Gehaxelts Blog

Vor einigen Tagen laß ich in meinem Mathebuch im Kapitel Kryptographie etwas über das RSA-Verfahren. Ich wollte daraufhin versuchen, diesen nachzustellen.

Die Formeln bzw. eine grobe Anleitung war dort gegeben.

Was ist RSA

RSA ist ein, nach den Entwicklern Rivest, Shamir und Adleman benannter kryptographischer Algorithmus, welcher mit öffentlichen (public) und privaten (private) Schlüsseln arbeitet. Das ganze System asymmetrisch aufgebaut, d.h. man nutzt den öffentlichen Schlüssel zum Verschlüsseln einer Nachricht, welche nur mit dem geheimen privaten Schlüssel entschlüsselt werden kann. Die Stärke basiert darauf, dass man den privaten Schlüssel nur mit sehr hohem technischen Aufwand zurückrechnen kann.

Wie funktioniert RSA?

Zunächst müssen alle Kommunikationspartner ein Schlüsselpaar bestehend aus öffentlichem und privatem Schlüssel erstellen.

Der private Schlüssel muss geheim gehalten werden, denn damit ist die Entschlüsselung möglich. Die öffentlichen Schlüssel können problemlos unter den Kommunikationsteilnehmern ausgetauscht werden.

1. Möchte nun Alice eine Nachricht an Bob schicken, so muss Sie Bobs öffentlichen Schlüssel kennen.

2. Sie verschlüsselt die Nachricht mit Bobs öffentlichen Schlüssel.

3. Die Nachricht kann dann über einen ungesicherten Kanal an Bob übertragen werden.

4. Bob entschlüsselt die Nachricht mit seinem privaten Schlüssel.

Christopher, welcher die verschlüsselte Nachricht abfangen konnte, kann damit nichts anfangen, denn er besitzt nicht Bobs privaten Schlüssel. Dieser lässt sich auch nur schwer zurückrechnen.

Mathematik hinter RSA

Zu Anfang benötigt man zwei große Primzahlen mit mehreren Hundert stellen, wobei gelten muss, dass p != q.

• Primzahl p

• Primzahl q

Daraufhin kann man das RSA-Modul N und Phi(N) berechnen:

• N = p*q

• Phi(N) = (p-1)*(q-1)

Es folgt die Bestimmung einer Zahl e, welche zu Phi(N) teilerfremd ist. Dies geschieht mithilfe des ggT, und dabei gilt 1 < e < Phi(N):

• ggT(e, Phi(N)) = 1

e und N bilden den öffentlichen Schlüssel.

Zuletzt fehlt noch der private Schlüssel d, welches ein multiplikatives Inverses zu e ist:

• ed + kPhi(N) = 1 = ggT(e, Phi(N))

Damit hat man alle Voraussetzungen für eine Ver-/Entschlüsselung geschaffen.

Eine Nachricht T verschlüsselt man mit dem öffentlichen Schlüssel folgendermaßen:

• C = T^e % N

Das Chiffrat C lässt sich mit dem privaten Schlüssel wieder entschlüsseln:

• T = C^d % N

Das war dann auch schon der RSA-Algorithmus.

Meine Implementierung in Python

Im Großen und Ganzen besteht der RSA-Algorithmus aus größten gemeinsamen Teilern (ggTs), Potenzen, und Modulos.

Ich gebe zu, dass der Code nicht der schönste ist, da man einiges optimieren kann, z.B. ggT per Rekursion (was komischweise immer nur 0 brachte, da es einen Durchlaufen zu viel tat); die Funktion zur Berechnung des privaten Schlüssels,…

Es soll jedoch nur zum Lernzweck und Nachvollzug des RSA-Algorithmus dienen.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96

#Encoding: UTF-8
import random
# globale variable mit primzahlen
previous_primes = [2]

def gcd(a, b):
    '''Return the greatest common divisor (gcd) of two numbers.

Use the recursive variant of the extended Euclidean algorithm
to compute the GCD of a and b. Also find two numbers x and y
that satisfy ax + by = gcd(a,b).

'''
    if b == 0:
        return (a, 1, 0)
    (d_, x_, y_) = gcd(b, a % b)
    (d, x, y) = (d_, y_, x_ - (a // b) * y_)
    return (d, x, y)

#Funktion zur Überprüfung ob number eine Primzahl ist
def isPrime(number):
for prev_prime in previous_primes:
                if( 0 == (number % prev_prime)):
return False
return True

#Funktion zur Berechnung von Primzahlen
def gen_prime(max):
previous_primes = [2]
last_prime = 0
for i in xrange(2,max):
if(isPrime(i)):
previous_primes.append(i)
last_prime = i
return last_prime

def gen_privkey(p, q, e):
    ''' Return the private key exponent d.

Compute the private exponent d using the extended Euclidean algorithm.
d is the multiplicative inverse of e % ((p - 1) * (q - 1)),
so it satisfies d * e == 1 % ((p - 1) * (q - 1)).

'''
    phi_n = (p - 1) * (q - 1)
    (x, d, y) = gcd(e, phi_n)
    if d < 0: d += phi_n
    return d

#Funktion zur Verschlüsselung einer Zahl mit dem öffentlichen Schlüssel
def pubkey_encrypt(text, pubkey, factor):
return text ** pubkey % factor

#Funktion zur Entschlüsselung eines Chiffrats mit dem privaten Schlüssel
def privkey_decrypt(chiffre, privkey, factor):
return chiffre ** privkey % factor

print "Generating prime p"
prime_p = gen_prime(random.randint(10,50))
print ">>Prime p:" + str(prime_p)

print "Generating prime q"
prime_q = gen_prime(random.randint(10,50))
print ">>Prime q:" + str(prime_q)

assert prime_p != prime_q

print "Calculating factor n"
factor_n = prime_p*prime_q
print ">>Factor n:" + str(factor_n)

print "Calculating Phi(N)"
phi_n = (prime_p-1)*(prime_q-1)
print ">>Phi(N):" + str(phi_n)

# e doesn't have to be choosen at random. any prime number < phi_n will work.
e = 17
print ">>Public exponent e:" + str(e)

assert e < phi_n

print "Generating pubkey d"
privkey_d = gen_privkey(prime_p, prime_q, e)
print ">>Privkey d:" + str(privkey_d)

print "Generating text"
text_clear = random.randint(0,100)
print ">>Text:" + str(text_clear)

print "Encrypting"
text_encrypted = pubkey_encrypt(text_clear, e, factor_n)
print ">>Text (encrypted):" + str(text_encrypted)

print "Decrypting"
text_decrypted = privkey_decrypt(text_encrypted, privkey_d, factor_n)
print ">>Text (decrypted):" + str(text_decrypted)

Überarbeitung durch Ghost 21.10.2012

Den Code findet ihr auf GitHub.

Sollte jemand Optimierungen an dem Code durchführen, würde ich mich über eine Benachrichtigung freuen.

Gruß

gehaxelt