Low-Exponent-Angriff auf das RSA-Verfahren

Im Folgenden ist ein wesentlicher Angriff auf das RSA-Verfahren implementiert, der Low-Exponent-Angriff zur Entschlüsselung eines Klartextes m.

Der Exponent e des öffentlichen Schlüssels darf nicht zu klein sein, z.B. nicht e=3. Denn sonst ist unter bestimmten Voraussetzungen ein Low-Exponent-Angriff möglich.

Wird nämlich derselbe Klartext m an 3 verschiedene Empfänger geschickt, deren öffentliche Schlüssel (n, e) folgendermaßen lauten: (n₀, 3), (n₁, 3) und (n₂, 3), und werden die entsprechenden Geheimtexte c₀, c₁ und c₂ abgefangen, dann lässt sich mithilfe des chinesischen Restsatzes der Klartext m berechnen.

Denn es gilt

m³ kongruent c₀ (mod n₀)
m³ c₁ (mod n₁)
m³ c₂ (mod n₂)

Der chinesische Restsatz liefert dann eine eindeutige Lösung modulo n₀·n₁·n₂ für m³. Durch Ziehen der dritten Wurzel ergibt sich der Klartext m.

In der folgenden Implementierung wird zunächst die Ausgangssituation hergestellt (Funktion generateProblem). Es werden e RSA-Moduln n_i der Bitlänge r erzeugt, dann wird ein zufälliger Klartext m gewählt und jeweils mit (n_i, e) verschlüsselt, und dann werden die entstandenen Geheimtexte c_i "abgefangen".

Bei der Erzeugung der RSA-Moduln n_i wird dabei darauf geachtet, dass diese paarweise teilerfremd sind, und ferner, dass die jeweiligen φ(n_i) mit dem Exponenten e teilerfremd sind. Bei sehr großen Zahlen ist dies selbstverständlich, da es hochgradig unwahrscheinlich ist, wenn es nicht so wäre. Aber wir probieren das Programm ja zunächst mit kleineren Zahlenbeispielen aus, und daher ist diese Überprüfung erforderlich.

Es stehen somit am Ende eine Liste von e Moduln n_i und eine Liste von e Resten c_i als geeignete Eingabe für den Chinesischen-Restsatz-Algorithmus zur Verfügung. In der Funktion lowExponentAttack wird der Low-Exponent-Angriff durchgeführt.

Für das Ziehen der n-ten Wurzel aus einer ganzzahligen, sehr großen Kubikzahl ist ein eigener Algorithmus vorgesehen (Funktion nthRoot).

RsaLowExponentAttack.py

from random import *
from Basic import *
from Rsa import *


# erzeugt die Problemstellung fuer einen Low-Exponent-Angriff:
# eine Liste nn von e RSA-Moduln ni und eine Liste cc von
# zugehoerigen Geheimtexten ci, die durch Verschluesseln eines
# Klartextes m mit jeweils (ni, e) hervorgegangen sind
def generateProblem(r, e):
    # Liste nn von e RSA-Moduln ni der Bitlaenge r erzeugen,
    nn=getCoprimeModuli(r, e)
    #print nn
    # Klartext zufaellig erzeugen, m < alle ni
    m=randint(2, 2**(r-1)-1)
    print m    
    # m mit allen (n, e) verschluesseln
    cc=[]
    for ni in nn:
        cc+=[modexp(m, e, ni)]
    #print cc
    return nn, cc


# liefert eine Liste nn der Laenge e paarweise teilerfremder RSA-Moduln n,
# wobei zusaetzlich e teilerfremd zu den zugehoerigen phi(n) ist
def getCoprimeModuli(r, e):
    nn=[]    # RSA-Moduln n
    i=0
    while i<e:
        n, phi=getRsaN(r)      # (n, phi(n))
        if coprime(n, nn) and coprime(phi, [e]):
            nn+=[n]
            i+=1
    return nn


# ergibt true, wenn n zu den Elementen der Liste nn teilerfremd ist
def coprime(n, nn):
    for ni in nn:
        if ggt(n, ni)!=1:
            return False
    return True


# nn ist eine Liste von RSA-Moduln, cc die Liste von Geheimtexten,
# die durch Verschluesseln des Klartextes mit (ni, e) entstanden sind;
# e ist der fuer alle gleiche kleine Exponent, z.B. e=3
def lowExponentAttack(nn, cc, e):
    n, c=chineseRemainder(nn, cc)
    w=nthRoot(c, e)
    return w


# Chinesischer-Restsatz-Algorithmus
# Parameter: Liste nn von Moduln, Liste rr von Resten
# Rueckgabe: Modul, Rest
def chineseRemainder(nn, rr):
    if len(nn)==1:
        return nn[0], rr[0]
    else:
        j=len(nn)//2
        m, a=chineseRemainder(nn[:j], rr[:j])
        n, b=chineseRemainder(nn[j:], rr[j:])
        u=inverse(m, n)
        x=u*(b-a)%n*m+a
    return m*n, x


# wenn die Zahl c die n-te Potenz einer natuerlichen Zahl w ist,
# wird diese Zahl w berechnet und zurueckgegeben, ansonsten
# wird eine Exception ausgeloest
def nthRoot(c, n):
    # kleinste Zweierpotenz groesser als c bestimmen
    p=1
    while p**n<c:
        p*=2
    w=p
    wn=w**n
    # w binaer eingabeln
    while wn!=c:
        p//=2
        if p==0:
            raise Exception("%d ist keine %d-te Potenz" %(c, n))
        if wn>c:
            w-=p
        if wn<c:
            w+=p
        wn=w**n
    return w
    

if __name__=="__main__":
    r=200 # Bitlaenge von n
    e=3   # low exponent, z.B. 3, 5, 7, ..,
    # Problemstellung erzeugen
    nn, cc=generateProblem(r, e)
    # Low-Exponent-Angriff
    m=lowExponentAttack(nn, cc, e)
    print m