Kryptographie URL haftendorn.uni-lueneburg.de/mathe-lehramt/krypto/krypto.htm

[Kryptographie]  [Algebra]  [MuPAD]   © Prof. Dr. Dörte Haftendorn

Download mehrerer MuPAD-Notebooks dazu *.zip. 56 KB, winzig     Save Link Taget As..., Verküpfungs-Ziel speichern unter... Okamoto-Uchiyama-Public-Key-Verschlüsselung
Wesentliche Anregung: Seminararbeit von Kai Gehrs Universität Paderborn
MuPAD-Gruppe      acrowley@mupad.de     http://math-www.upb.de/~acrowley
Kryptographie mit MuPAD, Datei oka-uchi.mnb
Beispiel mit "echtem" Text und mittelgroßen Primzahlen zum Nachvollziehen
Für die Lehre aufbereitet Prof. Dr.Dörte Haftendorn, Mai 03
-----------------------------------------------------------------------------------

• read("C:/mathe-lehramt/krypto/oka-uchi/text_zahl_text.mu"): 

Vorbereitungsphase: Anton bereitet seine Schlüssel vor.
Festlegung einer Größennordnung, die die Nachrichten nicht überschreiten dürfen.
k= Bitlänge von p und etwa auch von q.

• k:=100:gross:=2^(k-1);

• pq:=proc(k) local zz ,p,q,gross;
        begin      gross:=2^(k-1);
          zz:= random(gross..2*gross);
          repeat
            p:=nextprime( zz());
            q:=nextprime( zz());
          until gcd(p,q-1)=1 and gcd(p-1,q)=1 and p<>q end_repeat;
        return([p,q]);
      end_proc:
  

• geheim:=pq(k); p:=geheim[1]: q:=geheim[2]:

Das ist Antons geheimer Schlüssel [p,q].

• //p:=7:  q:=5:

• n:=p*p*q;

• wahl_g:=proc(n,p) local g,zz;
            begin zz:= random(2..n);
              repeat 
                g:=zz()  
              until gcd(g,n)=1 and powermod(g,p-1,p^2)<>1 end_repeat;
              /* g aus Zn*, g^(p-1)<>1 mod p^2 */
              return(g);
            end_proc:

• g:=wahl_g(n,p);  //g:=31;

• gp:=powermod(g,(p-1),p^2) // Probe, darf nicht 1 sein

Für späteren Gebrauch rechnet er sich das Inverse modulo p des Logarithmus von gp aus.

• Lgp:= (gp-1) div p;
  Lgpinv:=modp([igcdex(Lgp,p)][2],p);
  Lgp*Lgpinv mod p;  //Probe, muss 1 sein

• g_alle:=[g,modp(g,p^2),modp(g,p),gp,Lgp, Lgpinv]:

• h:=powermod(g,n,n);

• public:=[n,g,h,k]:

Das ist Antons öffentlicher Schlüssel.
---------------------------------------------------------------------------------------
Anwendungsphase Verschlüsselung
Berta will Anton einen Text senden, den nur Anton lesen kann.
Sie beschafft sich Antons Public-Key:

• n:=public[1]:g:=public[2]:h:=public[3]:k:=public[4]:public:

• [p,q]

• m:=textToZahl("Medley 8h");  //Diese Nachricht ist vielleicht zu groß.

Sie bestimmt die Größe, die die Nachricht haben darf:

• k:=public[4]:  gross:=2^(k-1)

----------------

• //m:=2:
  gcd(m,n); // soll 1 sein

Sie wählt eine Zufallszahl

• zz:=random(1..n): r:=zz(); 

• c:=modp(powermod(g,m,n)*powermod(h,r,n),n);

Berta sendet an Anton den verschlüsselten Text c.
-----------------------------------------------------------------------------------------------
Anwendungsphase Entschlüsselung
Anton empfängt diesen verschlüsselten Text,
nimmt seinen geheimen Schlüssel und rechnet:

• cp:=powermod(c,p-1,p^2)

Hier darf jetzt nicht cp=1 stehen,

• if cp=1 then Lcp=0 else Lcp:=(cp-1) div p end_if;

• Lgpinv ;  //Hat er sich schon vorbereitet
  

Er erhält die Nachricht

• mm:=Lcp*Lgpinv mod p 

und wandelt die Nachricht in Klartext um.

• zahlToText(mm)

--------------------------------------------------------------------------------

[Kryptographie]  [Algebra]  [MuPAD]

Inhalt und Webbetreuung ©Prof. Dr. Dörte Haftendorn 2001, hier neu 2005, update 14. August 2011

Direkte Internetadressen [www.doerte-haftendorn.de] [haftendorn.uni-lueneburg.de/mathe-lehramt]    [haftendorn.uni-lueneburg.de/ing-math]