Zur Haupt­na­vi­ga­ti­on sprin­gen [Alt]+[0] Zum Sei­ten­in­halt sprin­gen [Alt]+[1]

Das RSA-Ver­fah­ren

 

Ab­schlie­ßend wird als real be­nutz­tes Ver­fah­ren das RSA-Ver­fah­ren im Rah­men des Ar­beits­blat­tes Das RSA-Ver­fah­ren vor­ge­stellt.

Be­mer­kung: Im Zu­sam­men­hang mit dem RSA-Ver­fah­ren kann auch der Schlüs­sel­aus­tausch nach Dif­fie-Hell­man als ein wei­te­res Bei­spiel für ein asym­me­tri­sches Ver­fah­ren be­han­delt wer­den. Dies ist auch aus his­to­ri­scher Sicht in­ter­es­sant. Wenn dies im Rah­men der RSA-Ein­heit the­ma­ti­siert wer­den soll (was durch­aus sinn­voll ist), so kann hier das Ar­beits­blatt 02_i­ud_a­b_a­sym_R­SA aus der Ein­heit „In­for­ma­ti­ons­ge­sell­schaft und Da­ten­si­cher­heit (iud)“ ver­wen­det wer­den.

Eine Liste ver­füg­ba­rer Prim­zah­len, bei denen noch mit ge­rin­gen Hilf­mit­teln ge­rech­net wer­den kann, fin­det man im In­ter­net, z.B. bei Wal­ter Fendt; eben­so ASCII-Ta­bel­len der Buch­sta­ben und Zah­len.

Um die Kom­ple­xi­tät zu re­du­zie­ren, wird hier in die­sem Un­ter­richts­gang le­dig­lich der Kom­mu­ni­ka­ti­ons­weg A → B be­trach­tet, nicht die bei­der­sei­ti­ge Kom­mu­ni­ka­ti­on. Nach­dem der Un­ter­richts­gang bis hier ver­folgt wurde, kann die Er­wei­te­rung auf eine bei­der­sei­ti­ge Kom­mu­ni­ka­ti­on auf­ge­setzt wer­den.

Tie­fer­ge­hen­de Hin­ter­grund­in­for­ma­tio­nen zu grund­le­gen­den Fra­gen:

Wie si­cher ist RSA?

Um den Al­go­rith­mus an­wen­den zu kön­nen, muss der Be­nut­zer das Pro­dukt ( p - 1 ) ( q - 1 ) ken­nen. Der öf­fent­li­che Schlüs­sel in­for­miert aber le­dig­lich über die Zahl N (be­stimmt als N = p · q ) und nicht über die bei­den er­zeu­gen­den Prim­fak­to­ren p und q selbst. Diese müss­ten eben über Fak­to­ri­sie­rung her­aus­ge­fun­den wer­den, Stich­wort „Ein­weg­funk­ti­on“.

In der Pra­xis setzt man also N aus so gro­ßen Prim­fak­to­ren zu­sam­men, dass die Zer­le­gung selbst mit leis­tungs­fä­hi­gen Com­pu­tern Jahre dau­ern würde (siehe Info in den Ar­beits­blät­tern).

Da das Pro­blem der Fak­to­ri­sie­rung prin­zi­pi­ell ge­löst wer­den kann, be­deu­tet das, dass RSA theo­re­tisch ge­se­hen nicht si­cher ist. Es dau­ert eben nach der­zei­ti­gem Stand der Tech­nik und Ma­the­ma­tik so lange, dass die In­for­ma­ti­on bis zum Zeit­punkt der Lö­sung nicht mehr re­le­vant ist (die­sen ge­ne­rel­len As­pekt von „Si­cher­heit“ lohnt es sich durch­aus, im Un­ter­richt zu the­ma­ti­sie­ren: Auch z.B. Tre­so­re wer­den mit einer Ga­ran­tie ver­kauft, wie lange sie un­be­fug­ten Öff­nungs­ver­su­chen wi­der­ste­hen kön­nen).

In die­ser Hin­sicht ist also RSA so­lan­ge si­cher, bis ein ent­spre­chend schnel­ler Al­go­rith­mus für die Prim­fak­tor­zer­le­gung ge­fun­den ist.

Be­mer­kung zu Dis­kre­pan­zen im Ver­gleich zu rea­lem RSA

Beim zur Ver­fü­gung ge­stell­ten Ar­beits­blatt wer­den je­weils nur ein­zel­ne Zah­len (näm­lich die De­zi­mal­codes der Buch­sta­ben nach der ASCII-Ta­bel­le) mit RSA ver­schlüs­selt.

  • In der Regel wer­den keine De­zi­mal-, son­dern He­xa­de­zi­mal­zah­len ver­wen­det. Für das RSA-Prin­zip ist die­ser Un­ter­schied je­doch nicht von Be­deu­tung
  • In der Rea­li­tät macht eine RSA-Ver­schlüs­se­lung der ein­zel­nen Zei­chen kei­nen Sinn: Würde so ver­schlüs­selt wer­den, so er­gä­be sich eine ein­deu­ti­ge Zu­ord­nung der Klar- und Ge­heim­buch­sta­ben wie im mo­no­al­pha­be­ti­schen Fall. Dies würde die Er­run­gen­schaf­ten von RSA zu­nich­te ma­chen, da man nun mit einer ein­fa­chen Häu­fig­keits­ana­ly­se an­grei­fen könn­te. Das be­deu­tet, dass in der Rea­li­tät die ASCII-Codes mas­kiert wer­den müs­sen. Hier­zu gibt es ver­schie­dens­te Mög­lich­kei­ten, wobei sich eine häu­fig ge­brauch­te oder gar ein­heit­li­che Me­tho­de nicht an­ge­ben lässt. Eine mög­li­che sei hier be­schrie­ben (auf­bau­end auf Joa­chim Mohr, 06.07.2020):

    • Die Buch­sta­ben wer­den z.B. in 2er-Grup­pen zu­sam­men­ge­fasst. Die ASCII-Codes wer­den z.B. mas­kiert, indem man die Zahl des zwei­ten Buch­sta­bens mit einer Zahl mul­ti­pli­ziert, die grö­ßer ist als die größ­te zu ver­schlüs­seln­de Zahl (ASCII be­sitzt 255 Zei­chen, also Mul­ti­pli­ka­ti­on mit einer Zahl z > 255). Da­nach wird das Er­geb­nis zur ers­ten Zahl (des ers­ten Buch­sta­bens) ad­diert.

      Bei­spiel: Ver­schlüs­selt wer­den soll ZPG IMP.

      2er-Grup­pen:ZP GI MP.

      Nach der ASCII-Ta­bel­le er­gibt sich 136 126 117 119 123 126.

      Nun wird mas­kiert mit z.B. 256:

      136 + 126 · 256 = 32392

      117 + 119 · 256 = 30581

      123 + 136 · 256 = 34939

    • Diese Zah­len wer­den nun mit RSA ver- und ent­schlüs­selt. Um die ur­sprüng­li­che Kom­bi­na­ti­on wie­der zu er­hal­ten, be­stimmt man (hier am ers­ten Bei­spiel durch­ge­führt) 32392  mod  256 = 136 , be­stimmt dar­aus den Fak­tor 126 und hat so beide ur­sprüng­li­chen ASCII-Codes zu­rück­ge­won­nen. Ein aus­führ­li­ches Bei­spiel ist unter der o.g. Quel­le ein­seh­bar.
  • Hier sind wei­te­re Mög­lich­kei­ten denk­bar, z.B. die Zu­sam­men­fas­sung grö­ße­rer Buch­sta­ben­grup­pen mit der Mas­kie­rung durch Mul­ti­pli­ka­ti­on mit Po­ten­zen der ge­wähl­ten Zahl. Bsp.: ZPG IMP mit 3er-Grup­pen und ge­wähl­ter Zahl 301 er­gibt die mit RSA zu ver­schlüs­seln­den Zah­len:

    136 + 126 · 301 + 117 · 301 2 = 10.638.379 und

    119 + 123 · 301 + 126 · 301 2 = 11.452.868

    De­mas­kie­rung würde hier er­fol­gen (am ers­ten Bei­spiel) durch 10.638.379  mod  301 2 und an­schlie­ßend den er­hal­te­nen Rest mod  301 in­klu­si­ve der Be­stim­mung der Fak­to­ren 117 im ers­ten Schritt und 126 im zwei­ten Schritt.

Das RSA-Ver­fah­ren durch­zu­füh­ren ist mit den be­spro­che­nen In­hal­ten nun pro­blem­los mög­lich. Schwie­ri­ger wird es je­doch, wenn man die Frage nach dem grund­le­gen­den ma­the­ma­ti­schen Fun­da­ment des RSA-Ver­fah­rens stellt: Warum funk­tio­niert RSA? Wel­che Zu­sam­men­hän­ge müs­sen dazu be­wie­sen wer­den? Hier­bei stößt man sehr schnell an die Gren­zen des­sen, was in der Schu­le mach­bar ist.

Hier als An­re­gung ei­ni­ge grund­le­gen­den Sätze und der Be­weis zur Kor­rekt­heit von RSA:

Grund­le­gen­de Sätze

  1. Die Euler'sche φ -Funk­ti­on

    Ist n eine na­tür­li­che Zahl, so gibt φ ( n ) die An­zahl der zu n teiler­frem­den Zah­len an, die nicht grö­ßer als n sind. Damit ist ins­be­son­de­re klar: Ist p eine Prim­zahl, so ist p teiler­fremd zu den Zah­len 1 bis p - 1 . Daher gilt für Prim­zah­len p φ ( p ) = p 1 . Für teiler­frem­de Zah­len m und n gilt: φ ( n ) φ ( m ) = φ ( n m ) . Daher gilt für Prim­zah­len p und q : φ ( p q ) = φ ( p ) φ ( q ) = ( p 1 ) ( q 1 ) . Be­wei­se zur Euler'schen φ -Funk­ti­on sind sehr lang­wie­rig und in die­sem Zu­sam­men­hang nicht wei­ter­füh­rend. Des­halb sei hier für In­ter­es­sier­te auf die gän­gi­ge Fach­li­te­ra­tur ver­wie­sen.

  2. Der Satz von Fer­mat-Euler und der klei­ne Satz des Fer­mat

    Satz von Fer­mat-Euler: Für a , m gilt: ggT ( a , m ) = 1 a φ ( m ) 1  mod  m

    Einen Spe­zi­al­fall davon stellt der klei­ne Fer­mat'sche Satz dar:

    Ist p eine Prim­zahl und a , gilt: ggT ( a , p ) = 1 a p - 1 1  mod  p .

    Bem.: Satz von Fer­mat-Euler für m = p , da φ ( q ) = ( p 1 )

    Der Be­weis des Sat­zes von Fer­mat-Euler geht über das in Klas­se 10 Mög­li­che hin­aus. Eine mög­li­che kom­bi­na­to­ri­sche Va­ri­an­te (als „Ket­ten­bas­teln“) kann evtl. für sehr in­ter­es­sier­te SuS the­ma­ti­siert wer­den. Diese und ei­ni­ge wei­te­re Be­weis­mög­lich­kei­ten fin­det man unter https://​de.​wi­ki­books.​org/​wiki/​Bew​eisa​rchi​v:_​Zah​lent​heor​ie:_​Ele­men­ta­re_​Zah​lent​heor​ie:_​Klei­ner_​Satz_​von_​Fer­mat

Der Be­weis: Warum funk­tio­niert RSA?

Die Be­wei­se zur theo­re­ti­schen Be­grün­dung der Kor­rekt­heit des RSA-Ver­fah­rens sind eben­falls oft auf­wän­dig und ma­the­ma­tisch in der Schu­le nicht durch­führ­bar. Hier je­doch eine mög­li­che Skiz­ze, die man (unter Aus­las­sung der Be­wei­se zur Euler'schen Funk­ti­on) schritt­wei­se nach­voll­zie­hen kann:

Die Bot­schaft B wird zum Ge­heim­text S ver­schlüs­selt durch Be­rech­nung von B e  mod  N ( = S ) . Die Ent­schlüs­se­lung wird vor­ge­nom­men durch S d  mod  N ( = B ) . Also gilt: S d  mod  N = ( B e  mod  N ) d  mod  N = B e d  mod  N .

Dabei war d das (mo­du­la­re) mul­ti­pli­ka­ti­ve In­ver­se zu e be­züg­lich mod  ( p 1 ) ( q 1 ) und es gilt: ( e d )  mod  φ ( N ) = 1 ( ( e d )  mod  φ ( p q ) = ( e d )  mod  ( p - 1 ) ( q - 1 ) = 1 ) .

Mit N = p · q und φ ( p · q ) = ( p - 1 ) · ( q - 1 ) gilt die die Be­zie­hung: e · d = k · φ ( N ) + 1 = k · φ ( p · q ) + 1 = k · ( p - 1 ) · ( q - 1 ) + 1 und somit: e · d  mod  φ ( N ) = ( k · ( p - 1 ) · ( q - 1 ) + 1 )  mod  φ ( N ) .

Wir er­in­nern uns: Der ent­schlüs­sel­te Ge­heim­text war: S d  mod  N = ( B e ) d = B e d  mod  N .

Wenn RSA funk­tio­nie­ren soll, muss also gel­ten: B e d  mod  N = B . Mit der obi­gen Be­zie­hung: e · d = k · ( p - 1 ) · ( q - 1 ) + 1 muss also gel­ten: B k · ( p - 1 ) · ( q - 1 ) + 1  mod  N = B .

Zu­sam­men­fas­send die zu be­wei­sen­de zen­tra­le Aus­sa­ge (Kor­rekt­heit von RSA):

Es seien p , q ver­schie­de­ne Prim­zah­len und B  mit  B < p · q .

Dann gilt für jede Zahl k : B k · ( p - 1 ) · ( q - 1 ) + 1  mod  p q = B .

Be­weis1: Zu­nächst ge­trennt nach den Prim­zah­len p und q (1), (2), dann Zu­sam­men­füh­rung (3):

  1. B k · ( p - 1 ) · ( q - 1 ) + 1  mod  p = B
  2. B k · ( p - 1 ) · ( q - 1 ) + 1  mod  q = B
  3. B k · ( p - 1 ) · ( q - 1 ) + 1  mod  p q = B
Zu:
  1. Mit den ele­men­ta­re Po­tenz­re­gel a n + m = a n a m und ( a m ) n = a m n folgt: B k · ( p - 1 ) · ( q - 1 ) + 1 = B · B k · ( p - 1 ) · ( q - 1 ) = B · ( B ( p - 1 ) ) k ( q - 1 ) .

    Mit den Re­geln für mo­du­la­res Po­ten­zie­ren, dem klei­nen Fer­mat'schen Satz ggT ( p , B ) = 1 B p - 1 1  mod  p sowie ggT ( p , B ) = 1 , da p Prim­zahl und B < p ist, folgt: B k · ( p - 1 ) · ( q - 1 ) + 1  mod  p = B · ( B p - 1 ) k · ( q - 1 )  mod  p = B · ( B p - 1  mod  p ) k · ( q - 1 )  mod  p = B · ( 1  mod  p ) k · ( q - 1 )  mod  p = B · 1 k · ( q - 1 )  mod  p = B  mod  p .

    Zu­sam­men­fas­send: B k · ( p - 1 ) · ( q - 1 ) + 1  mod  p = B  mod  p .

  2. Für q ana­log, le­dig­lich mit an­de­rer Sor­tie­rung im Ex­po­nen­ten.

    Zu­sam­men­fas­send: B k · ( p - 1 ) · ( q - 1 ) + 1  mod  q = B  mod  q .

  3. N = p q : Hier­zu füh­ren wir der Über­sicht­lich­keit hal­ber ein h := k · ( p - 1 ) · ( q - 1 ) + 1 .

    In den bei­den in (1) und (2) er­hal­te­nen Glei­chun­gen B h  mod  p = B  mod  p und B h  mod  q = B  mod  q brin­gen wir je­weils B auf die an­de­re Seite und er­hal­ten: B h  mod  p B  mod  p = 0 und B h  mod  q B  mod  q = 0 .

    Mit An­wen­dung der Regel über mo­du­la­re Ad­di­ti­on folgt: ( B h - B )  mod  p = 0 und ( B h - B )  mod  q = 0 . So­wohl p als auch q tei­len also B h - B .

    p und q sind je­doch ver­schie­de­ne Prim­zah­len, also muss ( p · q ) die Zahl B h - B tei­len.

    Mit den Re­chen­re­gel für mo­du­la­res Ad­die­ren und B < p q gilt damit: ( B h B )  mod  ( p · q ) = 0 B h  mod  ( p · q ) B  mod  ( p · q ) = 0 B h  mod  ( p · q ) B = 0 B h  mod  ( p · q ) = B

Die ein­zel­nen Schrit­te sind so mit den im Ver­lauf des Un­ter­richts be­wie­se­nen Ge­set­zen be­grün­det nach­voll­zieh­bar. Al­ler­dings bleibt der Be­weis auf­wän­dig.

 

1 An­ge­lehnt an http://​www.​ma­the­ma­tik-​netz.​de/​pdf/​RSA.​pdf.

 

Un­ter­richts­ver­lauf: Her­un­ter­la­den [odt][244 KB]

Un­ter­richts­ver­lauf: Her­un­ter­la­den [pdf][615 KB]

 

Wei­ter zu Ko­pier­vor­la­gen