Low-Exponent-Angriff auf das RSA-Verfahren

 aufwärts

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: (n0, 3), (n1, 3) und (n2, 3), und werden die entsprechenden Geheimtexte c0, c1 und c2 abgefangen, dann lässt sich mithilfe des chinesischen Restsatzes der Klartext m berechnen.

Denn es gilt

m3  kongruent  c0 (mod n0)
m3  kongruent  c1 (mod n1)
m3  kongruent  c2 (mod n2)

Der chinesische Restsatz liefert dann eine eindeutige Lösung modulo n0·n1·n2 für m3. Durch Ziehen der dritten Wurzel ergibt sich der Klartext m.

Implementierung

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

Bei der Erzeugung der RSA-Moduln ni wird dabei darauf geachtet, dass diese paarweise teilerfremd sind, und ferner, dass die jeweiligen φ(ni) 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 ni und eine Liste von e Resten ci 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

 

Weiter mit: up

 

homeH.W. Lang   Hochschule Flensburg   lang@hs-flensburg.de   Impressum   Datenschutz   ©   Created: 14.12.2016   Updated: 08.06.2018
Valid HTML 4.01 Transitional

Hochschule Flensburg
Campus Flensburg

Informatik in Flensburg studieren...

 

Neu gestaltetes Studienangebot:

Bachelor-Studiengang
Angewandte Informatik

mit Schwerpunkten auf den Themen Software, Web, Mobile, Security und Usability.

Ihr Abschluss
nach 7 Semestern:
Bachelor of Science

 

Ebenfalls ganz neu:

Master-Studiengang
Angewandte Informatik

Ein projektorientiertes Studium auf höchstem Niveau mit den Schwerpunkten Internet-Sicherheit, Mobile Computing und Human-Computer Interaction.

Ihr Abschluss
nach 3 Semestern:
Master of Science

 

Weitere Informatik-Studienangebote an der Hochschule Flensburg:

Medieninformatik

Wirtschaftsinformatik