RSA-krypto

Asymetrisk kryptering bygger på att man har två nycklar, en som är publik och en som är hemlig.  Sändaren använder den publika nyckeln för att kryptera och mottagaren använder den hemliga för att dekryptera. RSA är en sån algoritm. För beskrivning av teorin bakom den och andra algoritmer hänvisar jag till litteraturen och nätet. Det finns massor att läsa för den vetgirige.

Jag beskriver gången här eftersom algoritmen är väl känd och det är inget man behöver komma ihåg eller kan/ska uppfinna på egen hand. Därmed är det svårt att leda dig rätt med mindre än att man beskriver algoritmen och tillämpningen av den. Inte riktigt enligt pluggakutens regler men jag har svårt att se hur man skulle göra annars.

Säkerheten i alla algoritmer bygger på att de är väl kända och att många människor försökt knäcka dem baserat på den kunskapen. Det finns otaliga exempel på att man hittat svagheter i kryteringsalgoritmer på det här sättet.

 

Du har givet att produkten av två primtal (p,q) ska bli 55 och då har du hittat p=5 och q = 11. Normalt börjar med att välja 2 gigantiska primtal först och sen räkna ut produkten men här går det bra att göra det i uppgiftens ordning för det finns inte så många primtal under 55 att välja på. Häri  ligger styrkan i krypteringen, väljer man ett tillräckligt stort primtal och en produkt är det praktiskt svårt att beräkna det andra primtalet med dagens teknik. Kvantdatorer kan mycket väl ändra på det men då får man också andra, starkare, krypton att ta till.

Därefter beräknar du ett värde kallat Carmicheals totient function $\lambda \left(n\right)$ som beräknas som lcm(p-1,q-1) -> lcm(4,10) där lcm är least common multiple, dvs det lägst värdet som kan divideras av parametrarna. Det finns sätt att beräkna det när man har stora p,q men i det här fallet kan man utan att räkna inse att 20 är det värdet. 20 är jämnt delbart med 10 och 4 och något mindre sådant finns inte.

Sen väljer man vanligen en publik nyckel e som ska ha egenskapen att den är ett heltal 1<e<$\lambda \left(n\right)$ och att e, $\lambda$inte har någon annan gemensam faktor än 1. I det här fallet är den publika nyckeln given som e=17  och det verkar ju stämma med ovanstånde villkor.

 

För att sen beräkna den hemliga nyckeln d så ska den uppfylla

$1\equiv (e*d) mod (p-1,q-1)$

här

$1\equiv (17*d) mod 20$, dvs hitta det minsta d sådant att dess produkt med 17  dividerat med 20 har resten 1. I det här fallet blir det 13 om jag har räknat rätt.

Det var nycklarna där den publika består av krypteringsnyckel och produkten n (e,n) och den privata av den hemliga d och produkten n (d,n)

Dekryptering av ett meddelande innebär i regel att man får ett antal heltal där varje heltal representerar ett krypterat tecken. Det finns tekniker för att se till att ett tecken inte får samma kryptovärde varje gång det förekommer vilket gör det känsligt för statistiska angrepp.

Kryptering och dekryptering enligt RSA-algoritmen bygger på modulo så att

b=a^e mod n

och dekryptering

a = b^d mod n

Där a är det okrypterade tecknet och b det krypterade. I det här fallet blir alltså dekrypteringen

a = 5¹³ mod 55 = 15

Så svaret är d=13, a=15 om jag inte slarvat med siffrorna.

 

 

av det korta meddelandet b= 5 blir då

5¹³ mod 55 = 15

Så svaret på frågan är d=13 och a = 15

CurtJ skrev:

Asymetrisk kryptering bygger på att man har två nycklar, en som är publik och en som är hemlig.  Sändaren använder den publika nyckeln för att kryptera och mottagaren använder den hemliga för att dekryptera. RSA är en sån algoritm. För beskrivning av teorin bakom den och andra algoritmer hänvisar jag till litteraturen och nätet. Det finns massor att läsa för den vetgirige.

Jag beskriver gången här eftersom algoritmen är väl känd och det är inget man behöver komma ihåg eller kan/ska uppfinna på egen hand. Därmed är det svårt att leda dig rätt med mindre än att man beskriver algoritmen och tillämpningen av den. Inte riktigt enligt pluggakutens regler men jag har svårt att se hur man skulle göra annars.

Säkerheten i alla algoritmer bygger på att de är väl kända och att många människor försökt knäcka dem baserat på den kunskapen. Det finns otaliga exempel på att man hittat svagheter i kryteringsalgoritmer på det här sättet.

 

Du har givet att produkten av två primtal (p,q) ska bli 55 och då har du hittat p=5 och q = 11. Normalt börjar med att välja 2 gigantiska primtal först och sen räkna ut produkten men här går det bra att göra det i uppgiftens ordning för det finns inte så många primtal under 55 att välja på. Häri  ligger styrkan i krypteringen, väljer man ett tillräckligt stort primtal och en produkt är det praktiskt svårt att beräkna det andra primtalet med dagens teknik. Kvantdatorer kan mycket väl ändra på det men då får man också andra, starkare, krypton att ta till.

Därefter beräknar du ett värde kallat Carmicheals totient function $\lambda \left(n\right)$ som beräknas som lcm(p-1,q-1) -> lcm(4,10) där lcm är least common multiple, dvs det lägst värdet som kan divideras av parametrarna. Det finns sätt att beräkna det när man har stora p,q men i det här fallet kan man utan att räkna inse att 20 är det värdet. 20 är jämnt delbart med 10 och 4 och något mindre sådant finns inte.

Sen väljer man vanligen en publik nyckel e som ska ha egenskapen att den är ett heltal 1<e<$\lambda \left(n\right)$ och att e, $\lambda$inte har någon annan gemensam faktor än 1. I det här fallet är den publika nyckeln given som e=17  och det verkar ju stämma med ovanstånde villkor.

 

För att sen beräkna den hemliga nyckeln d så ska den uppfylla

$1\equiv (e*d) mod (p-1,q-1)$

här

$1\equiv (17*d) mod 20$, dvs hitta det minsta d sådant att dess produkt med 17  dividerat med 20 har resten 1. I det här fallet blir det 13 om jag har räknat rätt.

Det var nycklarna där den publika består av krypteringsnyckel och produkten n (e,n) och den privata av den hemliga d och produkten n (d,n)

Dekryptering av ett meddelande innebär i regel att man får ett antal heltal där varje heltal representerar ett krypterat tecken. Det finns tekniker för att se till att ett tecken inte får samma kryptovärde varje gång det förekommer vilket gör det känsligt för statistiska angrepp.

Kryptering och dekryptering enligt RSA-algoritmen bygger på modulo så att

b=a^e mod n

och dekryptering

a = b^d mod n

Där a är det okrypterade tecknet och b det krypterade. I det här fallet blir alltså dekrypteringen

a = 5¹³ mod 55 = 15

Så svaret är d=13, a=15 om jag inte slarvat med siffrorna.

 

 

av det korta meddelandet b= 5 blir då

5¹³ mod 55 = 15

Så svaret på frågan är d=13 och a = 15

Tack för svaret och all information. 

Svaret är däremot; d=33  och a=15

 

Jag tror att man gör såhär:

vi har att; (p-1)(q-1)= 4·10=40 och vi ska beräkna 17d=1(mod 40).

 

40=17·2+6

17=6·2+5

6=5·1+1

 

1=6+5(-1)=6+(17+6(-2))(-1)=6·3+17(-1)=(40+17(-2))3+17(-1)=  40·3  +  17(-7)

 

Vi ser att d=-7=33(mod40)

Då är a=5^33(mod55)=8   men detta är ju fel för a=15. Men om jag gör  a=5^3(mod55)=15 då blir det rätt men varför ska jag upphöja 5 med 3 och inte 33? vart gör jag fel?

Ja du har helt rätt, jag slarvade där och ber om ursäkt för det. Som försvar så använder "man" alltid färdiga moduler när man skriver mjukvara som krypterar/dekrypterar. Av flera skäl men framför allt för att de är testade och klara så man inte skapar några kryphål vilket är lätt hänt annars och man kan räkna med att skurkar hittar dem. Själv använder jag Bouncy Castle men det finns många andra.

Det problem som slog dig i bakhuvudet är att du har beräknat 5^33 med begränsad precision så när du tar det talet modulus 55 så är det eg ett avrundat värde och storleken på avrundningen beror på vilket verktyg du använder.

Det enklaste sättet att hantera det på datorer med begränsad precision är att göra upphöjningen steg för steg och ta bort 55 från produkten så fort man kan.

Ett litet java-program kan se ut såhär

public static void main(String[] args) {
    System.out.println(decrypt(33,5,55));
}

private static int decrypt (int privateKey, int encryptedChar, int primesProduct) {
    int product = 1;
    for (int i = 0; i < privateKey; i++) {
        product *= encryptedChar;
        while (product > primesProduct) {
            product -= primesProduct;
        }
    }
    return product;
}  

eller motsvarande i python

def decrypt(d, b, n):
    prod = 1
    for i in range (1, d+1):
        prod *= b
        while prod>55:
            prod -=55

    return prod

print (decrypt(33,5,55))

 

Tack för att du rättade mig :)

jahha okej, tack själv!