inverse mod (RSA encrypting)

[Glimi]

Owkay ik weet niet of dit hier hoort maar ik wist niet precies waar het hoorde

Dit gaat over het RSA versleutelingsalgoritme

Ik moet 1 getal berekenen. Dit is bijv $D. De formule voor $D moet hieruit blijken

code:

($D*$E) mod ($P-1)*($Q-1);

$P == een random priemgetal
$Q == een random priemgetal
$Z == ($P-1)*($Q-1)
$E == relatief priem tov ($P-1)*($Q-1)

Op dit moment bereken ik $D als volgt:

code:

function inv_mod($E, $Z){
    

    $D=1;

      // $Z == ($P-1)*($Q-1)
    while(TRUE){
        if(($D*$E) % $Z ==1){
            return($D);
        }
        $D++;
    }
    
}

Ik probeer dus gewoon alle D's uit. Echter volgens mij moet dit makkelijk met een ander algoritme kunnen. Ik heb nu dit algoritme:

$E == relatief priem tov ($P-1*($Q-1) == (($P-1)*($Q-1))-1 is altijd relatief priem

code:

function inv_mod($E, $Z){
    
      define("Multiplier_MIN",1);
      define("Multiplier_MAX",<waarde>); 
      
    $multiplier = mt_rand(Multiplier_MIN, Multiplier_MAX);

     //(($multiplier*$Z)+1)*$E*$E) % $Z ==1
      $D = (($multiplier*$Z)+1);
      return($D);
    
}

Wat ik nu doe is het relatief priem getal in het kwadraat. Als je dit deelt door $Z krijg je altijd 1. Echter om er wat variatie in te brengen (anders weet je gelijk met de public key wat de private key is) moet hij maal een getal. Proef ondervindelijk heb ik gevonden dat als je $E^2 vermenigvuldigt met (een random getal maal $Z +1), dat je dan ook altijd 1 als rest overhoudt.

Nou vraag ik me af, zit er een grote fout in dit algoritme? En het belangrijkste, kan iemand dit THEORETISCH uitleggen

Superveel dank, en sorry voor de lap tekst

Persoonlijk lijkt me deze manier van $D generen niet snel te cracken omdat je $P*$Q weggeeft in je public key en ($P-1)*($Q-1) moeilijk te achterhalen is

[Verwijderd]

geen idee, maar schematisch weergegeven ziet 't er zo uit:

code:

p=5, q=7             bedenk 2 grote priemgetallen
N = 35               p*q
gcd(5,24) = 1 
(pepaal e, waarbij e>1)     gcd(e,(p-1)(q-1)) = 1 (e>1)
5 = 5^-1 % 24           d = e^-1 % (p-1)(q-1)
verstuur het getal 33:      encrypt x
33^5 % 35 = 3           x^e % N = y
verstuur 3          verstuur y
ontvang:            decrypt y
3^5 % 35 = 33           y^d % N = x

[DroogKloot]

Toevallig ben ik ook met een RSA-script bezig voor mIRC, ik loop echter tegen een ander probleem aan: mIRC heeft de beperking dat het getallen van > 40 cijfers intern berekent (EN weergeeft) in wetenschappelijke notatie, waardoor bij het encrypten een compleet verkeerde uitkomst wordt gereturned. Anyway, ik zal proberen het algorithme uit te leggen...

A). Neem twee willekeurige priemgetallen P en Q, beide van bitgrootte X (decimaal P en Q zijn dus maximaal 2 ^ (X - 1) groot).
. Noem het product van (P * Q) N, dit is de modulus. Niet te verwarren met de modulusfunctie die later aan bod komt.
C). Zoek een getal E kleiner dan N, dat geen gemeenschappelijke factoren heeft met ((P - 1) * (Q - 1)); met andere woorden, de grootste gemeenschappelijke deler van E en ((P - 1) * (Q - 1)) moet 1 zijn.
D). Zoek een getal D zo, dat ((E * D) - 1) deelbaar is door ((P - 1) * (Q - 1). Met andere woorden, ((E * D) - 1) is een veelvoud van ((P - 1) * (Q - 1)) en de deling moet als resultaat een integer opleveren.

E en D zijn de public respectievelijk private exponenten, (N, E) is de public key en (N, D) is de private key. Hierbij snap ik overigens niet wat er bedoeld wordt met de notatie (N, E): de modulus van N en E, of de GCD van N? En stel de public key is X bits groot, wordt dan bedoeld dat N en E (achter elkaar geschreven) X bits groot zijn, of N en E afzonderlijk?

Encryptie: Alice neemt beide public key factoren van Bob en versleutelt haar bericht volgens de formule C = (M ^ E) modulus N; waarbij M niet het hele bericht voorstelt, maar een string (van dezelfde grootte als de public key) ASCII-waardes. Is de PK b.v. acht bits lang, dan wordt een blok van acht karakters - ieder karakter afzonderlijk geconverteerd naar bijbehorende ASCII-waarde en vervolgens achter elkaar genoteerd - uit het bericht M genomen, waarna het resulterende getal tot E verheven wordt. Dit gaat zo door totdat alle blokken door de molen zijn gehaald. ***

Decryptie: Bob ontcijfert de cyphertext C met zijn private exponent (D) en de formule M = (C ^ D) modulus N; uit C destilleert hij ieder blok en zet dat om in de oorspronkelijke ASCII-string.

*** Ben hier niet zeker van, het zou ook kunnen dat het gehele bericht in EEN grote string van ASCII-waardes gegoten wordt en daarna tot E verheven.

[Verwijderd]

zeg, die alice en bob komen me errug bekend voor !!!
zit je soms op de Hogeschool van Utrecht?

http://www.icim.fnt.hvu.nl/vak/3widi1/Week14/Coll14.doc

[Verwijderd]

Op zaterdag 10 november 2001 13:23 schreef Glimi_ie het volgende:
Owkay ik weet niet of dit hier hoort maar ik wist niet precies waar het hoorde

Dit gaat over het RSA versleutelingsalgoritme

Ik heb nu dit algoritme:

$E == relatief priem tov ($P-1*($Q-1) == (($P-1)*($Q-1))-1 is altijd relatief priem

code:

function inv_mod($E, $Z){
    
      define("Multiplier_MIN",1);
      define("Multiplier_MAX",<waarde>); 
      
    $multiplier = mt_rand(Multiplier_MIN, Multiplier_MAX);

     //(($multiplier*$Z)+1)*$E*$E) % $Z ==1
      $D = (($multiplier*$Z)+1);
      return($D);
    
}

Wat ik nu doe is het relatief priem getal in het kwadraat. Als je dit deelt door $Z krijg je altijd 1. Echter om er wat variatie in te brengen (anders weet je gelijk met de public key wat de private key is) moet hij maal een getal. Proef ondervindelijk heb ik gevonden dat als je $E^2 vermenigvuldigt met (een random getal maal $Z +1), dat je dan ook altijd 1 als rest overhoudt.

Nou vraag ik me af, zit er een grote fout in dit algoritme? En het belangrijkste, kan iemand dit THEORETISCH uitleggen

Tja, volgens mij is dit THEORETISCH gezien wel in orde. Maar praktisch... Om een beetje security te hebben moeten P en Q en dus P*Q en dus ook (P-1)*(Q-1) heel groot zijn. Jij stelt nu voor om als private (of public) key een veelvoud van (P-1)*(Q-1) te nemen plus 1. Weet je wat je met die key moet doen?! Je moet een getal tot de macht van je private key nemen modulo P*Q. Dus jij gaat ff x^D mod P*Q uitrekenen met D een veelvoud van een getal van honderden bits. Als je dat doet ben je jaren bezig om een bericht te versleutelen of ontsleutelen. Dus THEORETISCH => ja, PRACTISCH => NO FUCKING WAY.

Oplossing: Je zoekt een D waarvoor geldt dat:
D*E = 1 % Z oftewel:
D*E + n*Z = 1.
Als je nu het uitgebreide algoritme van Euclides op E en Z loslaat geeft ie als GCD 1 (dat moet je ook hebben) maar verder geeft ie je ook nog de waarden D en n. n kun je weggooien, maar D is precies wat je zoekt. En dit algoritme zal je ook een D geven die niet zo associaal groot is als de gene die jij voorstelde

M.a.w. Google => "Extended GCD" of "Uitgebreide algoritme van Euclides"

[Glimi]

Op maandag 12 november 2001 00:25 schreef Xalista het volgende:

[..]

Tja, volgens mij is dit THEORETISCH gezien wel in orde. Maar praktisch... Om een beetje security te hebben moeten P en Q en dus P*Q en dus ook (P-1)*(Q-1) heel groot zijn. Jij stelt nu voor om als private (of public) key een veelvoud van (P-1)*(Q-1) te nemen plus 1. Weet je wat je met die key moet doen?! Je moet een getal tot de macht van je private key nemen modulo P*Q. Dus jij gaat ff x^D mod P*Q uitrekenen met D een veelvoud van een getal van honderden bits. Als je dat doet ben je jaren bezig om een bericht te versleutelen of ontsleutelen. Dus THEORETISCH => ja, PRACTISCH => NO FUCKING WAY.

Oplossing: Je zoekt een D waarvoor geldt dat:
D*E = 1 % Z oftewel:
D*E + n*Z = 1.
Als je nu het uitgebreide algoritme van Euclides op E en Z loslaat geeft ie als GCD 1 (dat moet je ook hebben) maar verder geeft ie je ook nog de waarden D en n. n kun je weggooien, maar D is precies wat je zoekt. En dit algoritme zal je ook een D geven die niet zo associaal groot is als de gene die jij voorstelde

M.a.w. Google => "Extended GCD" of "Uitgebreide algoritme van Euclides"

Zo'n id had ik ook al , maar van het algoritme van Euclides had ik nog nooit gehoord

Owkay superveel dank en ik ben gone goochelen (I'm feeling luckeeeeey!)

[DroogKloot]

Weet ik ondertussen nog steeds niet of je het hele bericht tegelijk encrypt (1 lange ASCII-string dus), of slechts in blokken van bitgrootte n (waarbij n gelijk is aan het aantal bits waaruit N (of is het D... of E?) bestaat)

[Glimi]

Op maandag 12 november 2001 23:10 schreef Nephilin het volgende:
Weet ik ondertussen nog steeds niet of je het hele bericht tegelijk encrypt (1 lange ASCII-string dus), of slechts in blokken van bitgrootte n (waarbij n gelijk is aan het aantal bits waaruit N (of is het D... of E?) bestaat)

Vooruit eventjes terug van het goochelen om je te verklappen dat ik daar nog niet helemaal uit ben. Ik gebruik nu maar 16 bits (2xASCII) maar ik zoek nog manieren om dit te vergrootten

[Verwijderd]

Op maandag 12 november 2001 23:10 schreef Nephilin het volgende:
Weet ik ondertussen nog steeds niet of je het hele bericht tegelijk encrypt (1 lange ASCII-string dus), of slechts in blokken van bitgrootte n (waarbij n gelijk is aan het aantal bits waaruit N (of is het D... of E?) bestaat)

Je kunt nooit een ASCII string encrypten die langer is dan je modulus want:

(string^D % Z) <= Z voor elke D.

Je geëncrypte string zou dus door te encrypten korter worden, iig leidt dit tot verlies van informatie, iets wat je niet kunt hebben. Wat je in de praktijk vaak ziet vaak ziet is dat de zender een private key bedenkt voor een sysmetrisch algoritme (b.v. 128 bit key voor RC5) daarmee zijn bericht encrypt (RC5 is een blockcypher, werkt dus op brokjes van je tekst) en vervolgens met b.v. RSA die key encrypt en aan het versleutelde bericht hecht.

De ontvanger ontsleuteld de sleutel en decrypt daarmee de eigenlijke tekst.

[Glimi]

Op dinsdag 13 november 2001 09:34 schreef Xalista het volgende:

[..]

Je kunt nooit een ASCII string encrypten die langer is dan je modulus want:

(string^D % Z) <= Z voor elke D.

Je geëncrypte string zou dus door te encrypten korter worden, iig leidt dit tot verlies van informatie, iets wat je niet kunt hebben. Wat je in de praktijk vaak ziet vaak ziet is dat de zender een private key bedenkt voor een sysmetrisch algoritme (b.v. 128 bit key voor RC5) daarmee zijn bericht encrypt (RC5 is een blockcypher, werkt dus op brokjes van je tekst) en vervolgens met b.v. RSA die key encrypt en aan het versleutelde bericht hecht.

De ontvanger ontsleuteld de sleutel en decrypt daarmee de eigenlijke tekst.

Dit is precies wat PGP doet. Hij doet dit omdat het coden van RSA-128 veels te veel tijd kost

Maar ik dacht dat ze hier vaker 3DES voor gebruiken?