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

Vigenère – Bre­chen

Man kann das Pro­blem in zwei Teile bzw. Schrit­te zer­le­gen:

  • Wie lang ist der Schlüs­sel?

  • Wenn die Schlüs­sel­län­ge be­kannt ist, wie kommt man dann auf den Schlüs­sel?

Hin­weis:

Das hier an­ge­wen­de­te Teile-und-herr­sche- Prin­zip ist eines der Grund­prin­zi­pi­en in der In­for­ma­tik:

Teile-und-herr­sche

Zer­le­ge ein schwie­ri­ges Pro­blem in Teil­pro­ble­me, die leich­ter zu lösen sind.

Da der zwei­te Teil der Pro­blem­lö­sung leich­ter er­scheint, be­ginnt man damit. Das hat aus di­dak­ti­scher Sicht Vor­tei­le, man kann aber eben­so mit der Be­stim­mung der Schlüs­sel­län­ge be­gin­nen.

Vigenère-Bre­chen - Schritt 2: Fin­den des Schlüs­sels bei be­kann­ter Schlüs­sel­län­ge

Grund­sätz­li­ches Vor­ge­hen:

Screenshot AB

An­nah­me: Die Länge des Schlüs­sel­worts ist be­kannt. Damit ist auch be­kannt, wel­che Buch­sta­ben gleich ver­schlüs­selt wer­den. Bei einem Schlüs­sel­wort der Länge drei wer­den also der 1., 4., 7., 10., … Buch­sta­be mit dem­sel­ben Cäsar-Schlüs­sel ver­schlüs­selt. Eben­so der 2., 5., 8., … und der 3., 6., 9., … Buch­sta­be.

Die Buch­sta­ben wer­den in so viele Grup­pen auf­ge­teilt, wie der Schlüs­sel lang ist. Mit einer Häu­fig­keits­ana­ly­se fin­det man in jeder Grup­pe den häu­figs­ten Buch­sta­ben. Das ent­spricht (wahr­schein­lich) dem 'E' (so­fern der Text in Deutsch oder Eng­lisch ver­fasst ist). Mit der Cäsar-Schei­be fin­det man nun leicht den Schlüs­sel­buch­sta­ben für jede Grup­pe. Das er­gibt das Schlüs­sel­wort.

Ma­te­ri­al:

  • 06_i­ud_a­b_Bre­chen­Teil2.odt (ev. die Strei­fen rechts und links vor­her ab­schnei­den)

Die SuS haben auf dem Ar­beits­blatt einen Kryp­to­text und ken­nen die Schlüs­sel­län­ge (4). Die Grup­pie­rung der Buch­sta­ben kann von den SuS sel­ber ge­macht wer­den. Al­ter­na­tiv be­kom­men die SuS die bei­den Strei­fen, links und rechts am Rand des Ar­beits­blat­tes (an den Punk­ten (...) zu­sam­men­kle­ben.) Jede Spal­te ent­spricht einer Buch­sta­ben-Grup­pe. Die SuS zäh­len ar­beits­tei­lig die Buch­sta­ben in je einer der Spal­ten (Teil­auf­ga­be a).

Wenn alle vier E's iden­ti­fi­ziert wur­den, er­mit­telt man leicht die ent­spre­chen­den vier A's. Diese bil­den das Schlüs­sel­wort (Teil­auf­ga­be b):

polyalph = mehrere monoalph

Vigenère-Schlüs­sel: MAUS

In Teil­auf­ga­be c) wird nun der Text mit dem ge­fun­de­nen Schlüs­sel­wort ent­schlüs­selt. Dies kann ent­we­der mit vier Cäsar-Schei­ben (ar­beits­tei­lig), mit der Vigenère-Ta­bel­le oder mit Cryp­Tool er­fol­gen.

Hin­weis:

Das Ar­beits­blatt kann je nach Grup­pe so um­ge­stal­tet wer­den, dass die SuS mehr oder we­ni­ger stark ge­führt wer­den.

Vigenère-Bre­chen - Schritt 1: Wie lang ist das Schlüs­sel­wort?

Ma­te­ri­al:

  • 07_i­ud_a­b_Bre­chen­Teil1.odt

Grund­sätz­li­ches Vor­ge­hen : Ka­si­ski-Test:

Wenn im Kryp­to­text eine Buch­sta­ben­fol­ge zwei­mal auf­tritt und wenn mit ihr das­sel­be Wort ver­schlüs­selt wurde, dann ist der Ab­stand zwi­schen den bei­den Buch­sta­ben­fol­gen die Schlüs­sel­län­ge oder ein Viel­fa­ches der Schlüs­sel­län­ge.

Bei­spiel1:

polyalph = mehrere monoalph

Man suche also nach mehr­fach vor­kom­men­den Buch­sta­ben­fol­gen und er­mit­te­le den Ab­stand.

Screenshot AB
  • 'DAS' kommt im Klar­text drei­mal vor. Im Kryp­to­text wird dar­aus­zwei­mal 'WAY' und ein­mal 'JTS'

  • Der Ab­stand der bei­den 'WAY's be­trägt 6. 6 = 2 ∙ 3 Der Schlüs­sel­könn­te also '2' oder '3' oder '6' Buch­sta­ben lang sein.

  • 'IAT' kommt im Kryp­to­text eben­falls zwei­mal vor und hat den­Ab­stand 15. 15 =5 ∙ 3

  • '3' kommt in bei­den Prim­fak­tor­zer­le­gun­gen vor und könn­te die Schlüs­sel­län­ge­sein.

  • Es ist na­tür­lich mög­lich, dass die Fol­gen nur zu­fäl­lig im Kryp­to­text gleichs­ind, im Klar­text aber nicht.

  • Lange Buch­sta­ben­fol­gen lie­fern mit grö­ße­rer Wahr­schein­lich­keit rich­ti­ge­Er­geb­nis­se als kurze.

Screenshot AB

Nach­dem das Prin­zip er­kannt wurde, su­chen die SuS in einem län­ge­ren Text (Auf­ga­be 2) nach wie­der­keh­ren­den Buch­sta­ben­fol­gen. Das kann von Hand auf dem Pa­pier er­fol­gen oder mit Hilfe eines Tools. Er­fah­rungs­ge­mäß wer­den auch beim hän­di­schen Vor­ge­hen genug Fol­gen ge­fun­den, um auf die Schlüs­sel­län­ge schlie­ßen zu kön­nen.

Al­ter­na­ti­ven / Zu­satz

Neben dem hän­di­schen Vor­ge­hen kann das Bre­chen der Vigenère-Ver­schlüs­se­lung auch mit Hilfe eines Tools er­fol­gen. Im ZPG-Ma­te­ri­al be­fin­den sich drei Tools zum Bre­chen mit­tels Au­to­kor­re­la­ti­on, mit­tels Ka­si­ski sowie mit­tels einer Brute-Force-Me­tho­de. Da­ne­ben sind auch zwei Tools aus dem In­ter­net er­wäh­nens­wert.

Wich­tig ist, dass die SuS das Vor­ge­hen ver­ste­hen und nicht nur das Tool ar­bei­ten las­sen.

  • ZPG-Ma­te­ri­al: 6_­soft­ware → An­griff­Vi­ge­ne­re_Au­to­kor­re­la­ti­on → Bre­ak­Vi­ge­ne­re.jar

Schritt 1
Schritt 2
 
  • ZPG-Ma­te­ri­al: 6_­soft­ware → An­griff­Vi­ge­ne­re_Ka­si­ski → Bre­ak­Vi­ge­ne­re.jar

    In Schritt 1 mar­kiert man im klei­nen Fens­ter links eine Buch­sta­ben­fol­ge, von der man ver­mu­tet, dass sie im Text häu­fi­ger vor­kommt. Im klei­nen Fens­ter rechts wer­den alle Vor­kom­men der Folge an­ge­zeigt. Durch An­kli­cken wird an­ge­zeigt, wel­chen Ab­stand die Folge links zur Folge rechts hat, und was die Prim­fak­to­ren die­ser Zahl sind. Macht man dies mit ei­ni­gen Buch­sta­ben­fol­gen und deren Ab­stän­den, kann man einen mög­li­chen Schlüs­sel ver­mu­ten und ein­tra­gen.

    Schritt 2 ist wie beim Au­to­kor­re­la­ti­ons-Tool.

    Kasiski
     
  • ZPG-Ma­te­ri­al: 6_­soft­ware → An­griff­Vi­ge­ne­re_par­ti­el­le­Bru­te­Force → Bre­ak­Vi­ge­ne­re.jar

    In Schritt 1 wird sys­te­ma­tisch jede Schlüs­sel­län­ge durch­pro­biert. Je­weils für den ers­ten Buch­sta­ben des Schlüs­sel­worts wird vom Tool ein Buch­sta­ben­häu­fig­keits­dia­gramm er­stellt (oben). Das ver­gleicht man mit dem Buch­sta­ben­häu­fig­keits­dia­gramm von deut­schen Tex­ten (unten). Stimmt es – bis auf eine Ver­schie­bung – über­ein, hat man die rich­ti­ge Schlüs­sel­län­ge ge­fun­den.

    Schritt 2 ist wie beim Au­to­kor­re­la­ti­ons-Tool.

    Kasiski
  • Mit dem Tool auf fol­gen­dem Link kann man in einem Text nach wie­der­keh­ren­den Buch­sta­ben­fol­gen der Länge 3 su­chen:

    http://​www.​staff.​uni-​mainz.​de/​pom­me­ren/​Kryp­to­lo­gie/​Klas­sisch/​2_​Po­ly­alph/​ka­sis­ki1.​html ( Ab­ge­ru­fen am 21.4.18)

  • Mit dem Tool auf die­ser Seite kann man in einem Text nach wie­der­keh­ren­den Buch­sta­ben­fol­gen mit ver­schie­de­nen Län­gen su­chen. Es wird auch der ggT an­ge­zeigt sowie das Er­geb­nis der Häu­fig­keits­ana­ly­se:

    https://​www.​do­mi­ni­kus-​gym­na­si­um.​de/​ka­si­ski-​test.​html ( Ab­ge­ru­fen am 21.4.18)

Im Ma­te­ri­al ist ein län­ge­rer ver­schlüs­sel­ter Text nebst Schlüs­sel und Ori­gi­nal­text ent­hal­ten. (07_i­ud_­Tex­t_lan­g_Bre­chen.odt)

An­sons­ten er­zeugt man Kryp­to­tex­te als Bei­spie­le für Schü­ler ein­fach mit Cryp­Tool 11.

Hin­weis:

Da bei der Ka­si­ski-Me­tho­de die Ab­stän­de in Prim­fak­to­ren zer­legt wer­den, ist es von Vor­teil, wenn in IMP-Mathe be­reits die Prim­fak­tor­zer­le­gung be­han­delt wurde (3.​1.​2.​1 Ma­the­ma­ti­sche Grund­la­gen der Kryp­to­lo­gie).

 


1 www.​cryp­tool.​org/ (Ab­ge­ru­fen am 21.4.18)

 

Un­ter­richts­ver­lauf: Her­un­ter­la­den [odt][1 MB]

Un­ter­richts­ver­lauf: Her­un­ter­la­den [pdf][1 MB]

 

Wei­ter zu One-Time-Pad (OTP)