This is not the document you are looking for? Use the search form below to find more!

Report home > Others

Cracking the Enigma Machine - Rejewski, Turing and the Math that saved the world

0.00 (0 votes)
Document Description
The Math That Saved the WorldBrad Youngbrad@clearpoint.co.ilA Mathematical and Historical Analysis of the Cryptographic Attacks on the Nazi Enigma Machine Marian RejewskiAlan TuringAgendaDevelopment…
File Details
Submitter
  • Name: inge

We are unable to create an online viewer for this document. Please download the document instead.

Cracking the Enigma Machine - Rejewski, Turing and the Math that saved the world screenshot
DOWNLOAD

Add New Comment




Related Documents

Apple and google use phone data to map the world by www.batteryfast.com

by: batteryfast, 3 pages

Apple and google use phone data to map the world by www.batteryfast.com

most dangerous cities in the world

by: whitneykydefaziorp, 2 pages

These adventurous souls have sought out the most dangerous cities in the world the people to live. And, once the stories started to get around the legends were born.

Unitech The World Spa South Call 9999189999

by: gupta22, 12 pages

Unitech World Spa - Unitech the World Spa South Gurgaon new residential project launch by Unitech Group. Unitech world spa is located at very prime location sector 30 & 41 at Gurgaon. ...

unitech the world spa 9811293151 unitech the world spa gurgaon

by: apr0030, 1 pages

unitech the world spa 9811293151 unitech the world spa gurgaon The World Spa is a new residential destination embellishing the address of Sectors 30 & 41, Gurgaon 9811293151.The most ...

unitech the world spa 9811293151 unitech the world spa gurgaon

by: may3, 1 pages

unitech the world spa 9811293151 unitech the world spa gurgaon The World Spa is a new residential destination embellishing the address of Sectors 30 & 41, Gurgaon 9811293151.The most ...

unitech the world spa 9811293151 unitech the world spa gurgaon

by: may004, 1 pages

unitech the world spa 9811293151 unitech the world spa gurgaon The World Spa is a new residential destination embellishing the address of Sectors 30 & 41, Gurgaon 9811293151.The most ...

How To Work From Anywhere In The World

by: mike1244, 1 pages

This PDF will give you an Inspiration about the main important question with regards to your current work situation, and should certainly be able to teach you exactly how working from anywhere in the ...

Ohio Country Journal- Around the World Gourmet Article

by: AroundTheWorldGourmet, 1 pages

An article from Ohio's Country Journal about Around the World Gourmet, an innovative producer of gluten free foods based in Columbus, OH.

Elementary Statistics Picturing the World, Larson Farber, Test Bank

by: georgesheslers, 48 pages

Elementary Statistics Picturing the World, Larson Farber, Test Bank

Elementary Statistics Picturing the World Larson 4th Edition Solutions Manual

by: georgesheslers, 48 pages

Elementary Statistics Picturing the World Larson 4th Edition Solutions Manual

Content Preview
  1. The Math That Saved the World
    Brad Young
    brad@clearpoint.co.il
    A Mathematical and Historical Analysis of the Cryptographic Attacks on the Nazi Enigma Machine
    Marian Rejewski
    Alan Turing
  2. Agenda
    Development of Enigma Machine – Why/How/What
    The Rejewski Crack
    The Turing Crack
    Historical Impact
  3. WWI Cryptology
    First major war with radio + telegraph
    Very large volume of communications
    Hand-ciphers
    Playfair, ADFGVX etc.
    Bigraph substitution + transformation
    Encryption/Decryption
    Inefficient …Became bottleneck
    Cryptanalysis
    Difficult, time-consuming…
    But successful (mainly)
  4. Zimmermann Telegram
  5. Invention of Enigma Machine
    Arthur Scherbius
    Efficient!
    (oh, and also Secure, by the way)
    Business, Military versions
    Early 1920’s – very poor sales
    German economy in trouble
  6. Oops
    Publishes history book
    Reveals the impact of crypto on WWI
    Now, the Germans want Enigma!
  7. A
    B
    C
    D
    E
    F
    G
    H
    Reflector
    3rd Rotor
    2nd Rotor
    1st Rotor
    Lightbulbs
    Keyboard
    Enigma Schematic
  8. A
    B
    C
    D
    E
    F
    G
    H
    Reflector
    Lightbulbs
    3rd Rotor
    2nd Rotor
    1st Rotor
    Keyboard
    Electric Circuit
  9. A
    B
    Pressing ‘A’ on the keyboard…
    C
    D
    E
    F
    … lights the ‘B’ lightbulb
    G
    H
    NOTE: Because it is a electric circuit, no letter can map to itself. Minor detail combinatorically speaking, but very important for the Turing crack.
    Reflector
    Lightbulbs
    3rd Rotor
    2nd Rotor
    1st Rotor
    Keyboard
    Electric Circuit
  10. A
    B
    C
    D
    E
    After each letter, the first rotor shifts one step.
    So now, pressing ‘A’ lights a different lightbulb….’F’
    F
    G
    H
    Reflector
    Lightbulbs
    3rd Rotor
    2nd Rotor
    1st Rotor
    Keyboard
    Rotor Shift
  11. A
    B
    C
    D
    E
    F
    Sits between keyboard and rotors.
    Each plug cable swaps signal between two letters.
    6 cables connect 12 letters. 14 other letters are not plugged at all.
    G
    H
    Reflector
    Lightbulbs
    Plugboard
    3rd Rotor
    2nd Rotor
    1st Rotor
    Keyboard
    Plugboard
  12. Plugboard
  13. Keysize
    A
    B
    Rotor Order
    Rotor Setting
    Plugboard
    Wiring
    I – III - II
    VYJ
    A/G, D/Q, J/Z,L/S, M/V, N/T
    3! = 6
    263 =17,576
    C(26,2) x C(24,2) x
    C(22,2) x C(20,2) x
    C(18,2) x C(16,2) x 1/6!
    (26!)3 x C(26,2)…C(2,2)x1/13!
    C
    ? 105
    D
    E
    F
    ? 1011
    ? 1092
    G
    H
    Total Key Size ? 10108
    Variable Key Size ? 1016
  14. German Use of Enigma
  15. German Use of Enigma
    Day Keys (RO, RS, PB) distributed monthly in key books
    • For each message, sender chooses Message Key (Rotor Setting only)
    Encode Message Key using Day Key, twice
    Move rotor to Message Key setting
    Encode actual message
    Set to Day Key(VYJ)
    Change to Message Key
    (CIL)
    CILCILATTACKFROMNORTHATNINETHIRTYBOKJRVSQIGPQTMNWJRAKOBYTKMTKGBBRQ
  16. Agenda
    Development of Enigma Machine – Why/How/What
    The Rejewski Crack
    The Turing Crack
    Historical Impact
  17. Biuro Szyfrów
    1918 – Polish Independence
    1919 – Creation (and success) of Cipher Bureau
    1926 – Germany goes dark as Enigma is adopted
    1930 – Bring in the mathematicians (?!?)
    Marian Rejewski
    Jerzy Ró?ycki
    Henryk Zygalski
  18. The Rejewski Crack
    Intuition,Espionage,Engineering
    Understand how Enigma works
    Reverse-engineer the wiring
    Be able to crack the key each day
    Permutational Mathematics
  19. The Math of Permutation Cycles
    P =
    P-1 =
  20. Cycle Notation
    P =
    P = (AECH)(BFD)(G)
    = (BFD)(G) (AECH)
    = (FDB)(G)(CHAE)
    P-1 = (HCEA)(DFB)(G)
    Benefits of cycle notation:
    Concise
    Easier to take inverse
    (These are benefits of efficiency)
  21. Cycle Structure
    = (AECH)(BFD)(G)
    P =
    4 3 1
    = (AFC)(BG)(D)(EH)
    Q =
    3 2 1 2
    Benefits of cycle notation:
    Concise
    Easier to take inverse
    Gives more info – Cycle Structure
    (This is a benefit of value-add information)
  22. Composition
    P =
    = (AECH)(BFD)(G)
    Q =
    = (AFC)(BG)(D)(EH)
    Q ? P = Q(P()) = (AHFDGBCE)
    Q ? P ? P ? Q - NOT Commutative
    Q ? ( P ? R ) = ( Q ? P ) ? R - Associative
  23. Identity
    = (A)(B)(C)(D)(E)(F)(G)(H)
    I =
    P ? I = I ? P = P
    P ? P -1 = I
    I ? I = I i.e. I = I -1
    (ab) ? I , but (ab) ? (ab) = (a)(b)
    i.e. (ab) = (ab)-1
  24. Conjugation
    Conjugation of Q by P is defined as P ? Q ? P-1
    P = (AECH)(BFD)(G)
    P-1 = (HCEA)(DFB)(G)
    Q = (AFC)(BG)(D)(EH)
    1-2-2-3
    1-2-2-3
    This is not a coincidence!
    This is not a coincidence!
    P ? Q ? P-1 = (AC)(B)(DHE)(FG)
  25. Theorem: Cycle structure is invariant under conjugation
    Proof:
    Suppose Q: i?j, that is Q(i) = j.
    Consider P ? Q ? P-1 (P(i)).
    P ? Q ? P-1 (P(i)) = P ? Q ? (P-1 ? P)(i)
    = P ? Q(i)
    = P(j)
    i.e. P ? Q ? P-1: P(i)?P(j)
    Therefore…
    If Q has k-cycle (i1, i2 … ik) then P ? Q ? P-1 has k-cycle (P(i1), P(i2)…P(ik))
    QED
  26. Using Permuation Cycles on Enigma
    A
    B
    Suppose we intercept a message: BOLJRVSQIGPQTMNWJRAKOBYTKMTTGBBRQUPWLHSOLNFEQTHJOVX
    Plaintext: abcabcCiphertext: BOLJRV
    Define En as the permutation that occurs when Enigma machine is in state n.
    So, in the first state, a?B. In the fourth state, a?J
    E1 = (aB …E4 = (aJ …
    Now…Recall the effect of the Reflector, which creates 2-letter circuits
    So, if a?B, then B?a. So the cycle is closed.
    E1 = (aB) …E4 = (aJ) …
    So, we can now compute E4 ? E1 = (BJ …
    C
    These are the variablesa,b,c, not the actual letters
    D
    E
    F
    G
    H
  27. Using Permuation Cycles on Enigma
    If we have many intercepts from the same day, then they were produced with the same day settings.
    So we can calculate the entire compositions…
    E4 ? E1 = (BJUMPWTCFE)(ARDNHSLYZK)(G)(I)(O)(Q)(X)(V)E5 ? E2 = (ORJCLVHGXKF)(AUYMPZQNDWB)(ES)(IT)E6 ? E3 = (BWOIKTZHXB)(EPQJYLVGN)(ARCU)(DSMF)
    Good news:
    abc variables have been eliminated!
    We’ve found a unique identifier!
    Bad news:
    It is one of 10,000,000,000,000,000 possibilities
  28. Explore the nature of En
    A
    B
    En = P ? Rn ? P where P is the plugboard permutation and Rn is rotor permutation when in state n
    E4 ? E1 = P ? R4 ? P ? P ? R1 ? P
    Now, recall the plugboard…
    P = (ab)(cd)(ef)(gh)(ij)(kl)(m)(n)(o)(p)(q)(r)(s)(t)(u)(v)(w)(x)(y)(z)
    All 2-cycles and 1-cycles, therefore P = P-1 !
    E4 ? E1 = P ? R4 ? P ? P ? R1 ? P
    = P ? R4 ? P ? P-1 ? R1 ? P
    = P ? R4 ? (P ? P-1 ) ? R1 ? P
    = P ? R4 ? R1 ? P
    = P ? (R4 ? R1 ) ? P
    = P ? (R4 ? R1 ) ? P-1
    C
    P
    R
    D
    E
    F
    G
    H
    Conjugation:Cycle structure of E4 ? E1 is same as cycle structure of R4 ? R1 and is not affected at all by the plugboard!
    E4 ? E1 = (BJUMPWTCFE)(ARDNHSLYZK)(G)(I)(O)(Q)(X)(V)E5 ? E2 = (AUYMPZQNDWB)(CLVHGXKFORJ)(ES)(IT)E6 ? E3 = (BWOIKTZHXB)(EPQJYLVGN)(ARCU)(DSMF)
    1-1-1-1-1-1-10-10 ; 2-2-11-11 ; 4-4-9-9
    Remember:
    Keysize(R) ? 105
    Keysize(P) ? 1011
  29. Now, where are we?
    Figuring out En is problem of size 1016
    Now, we have Rn, a smaller problem: 105
    Just barely small enough to attack brute force
  30. Building the Rejewski Dictionary
    RO RS E4 ? E1 E5 ? E2 E6 ? E3
    1 2 3 AAA 13-13 1-1-12-12 1-1-12-12
    1 2 3 BAA 1-1-12-12 1-1-12-12 2-2-11-11
    1 2 3 CAA 1-1-12-12; 2-2-11-11 1-1-12-12
    1 2 3 DAA 2-2-11-11 1-1-12-12 13-13
    1 2 3 EAA 1-1-12-12 13-13 13-13
    1 2 3 FAA 13-13 13-13 1-1-2-2-3-3-3-3-4-4
    1 2 3 GAA 13-13 1-1-2-2-3-3-3-3-4-4 2-2-5-5-6-6
    1 2 3 HAA 1-1-2-2-3-3-3-3-4-4 2-2-5-5-6-6 13-13
    1 2 3 IAA 2-2-5-5-6-6 13-13 4-4-9-9
    1 2 3 JAA 13-13 4-4-9-9 1-1-5-5-7-7
    1 2 3 KAA 4-4-9-9 1-1-5-5-7-7 13-13
    1 2 3 LAA 1-1-5-5-7-7 13-13 1-1-2-2-10-10
    1 2 3 MAA 13-13 1-1-2-2-10-10 1-1-1-1-11-11
    . . . . .
    . . . . .
    . . . . .
    …
    2-2-11-11; 1-1-1-1-1-1-1-1-4-4-5-5; 1-1-12-12 KFE 213
    2-2-11-11; 1-1-1-1-1-1-1-1-4-4-5-5; 2-2-5-5-6-6 ZTF 132
    2-2-11-11; 1-1-1-1-1-1-1-1-4-4-5-5; 5-5-8-8 GIC 312
    2-2-11-11; 1-1-1-1-1-1-1-1-9-9; 1-1-12-12 AHH 132
    2-2-11-11; 1-1-1-1-1-1-1-1-9-9; 1-1-12-12 WLA 312
    2-2-11-11; 1-1-1-1-1-1-1-1-9-9; 1-1-5-5-7-7 YKG 132
    2-2-11-11; 1-1-1-1-1-1-1-1-9-9; 13-13 DXI 213
    2-2-11-11; 1-1-1-1-1-1-1-1-9-9; 13-13 ESY 321
    2-2-11-11; 1-1-1-1-1-1-1-1-9-9; 13-13 VHX 213
    2-2-11-11; 1-1-1-1-1-1-1-1-9-9; 2-2-11-11 UNV 231
    …
    1 setting every 4 minutes, x 20 hours/day = 300 / day
    105 / 300 ? 1 year to complete
    Good news; Solved the RO, RS!
    Bad news: 105 solved, 1011 not solved
    Cycle structure is not unique
    …even though 105 << (1012)3 ? 1012
    But most have < 10
  31. Recovering the Plugboard
    Plugboard is the biggest problem combinatorically
    But… It is trivial to solve
    E4 ? E1 = (BJUMPWTCFE)(ARDNHSLYZK)(G)(I)(O)(Q)(X)(V)
    R4 ? R1 = (MGWTREFBJU)(AKZCINLSHY)(P)(D)(O)(Q)(V)(X)
    (BJUMPWTCFE)
    (BJUMGWTREF)
    Plugboard settings: P/G , C/R , E/F , etc.
  32. Paradox of Decreasing Benefit
    Keysize
    # Cables
  33. Agenda
    Development of Enigma Machine – Why/How/What
    The Rejewski Crack
    The Turing Crack
    Historical Impact
  34. 1939 – Brink of War
    Polish deliver Enigma replica and training to England and France
    Biuro Szyfrów is dismantled
  35. Bletchley Park
    HQ of British Government Code and Cypher School (GCCS)
  36. New Challenges
    Combinatoric
    More rotors to choose from
    Increase # of plugs
    Ring settings
    Procedural
    Eliminate Message Key repetition
    Navy / Air Force / Army mods
    Keysize now 1023
  37. Turing’s Solution
    Known-Plaintext attack
    Heil Hitler
    Wetterbericht
    Seeding values
    Plaintext Crib:Ciphertext:
    Try to place the crib without letter any letter mapping to itself
    WETTERBERICHT
    WETTERBERICHT
    WETTERBERICHT
    WETTERBERICHT
    WETTERBERICHT
    EXLMBTWZXBITWZCIQ
    P(false hit) = (25/26)length of crib
  38. Finding Cycles
    WETTERBERICHT
    EXLMBTWZXBITW
    E1: W?E
    E5: E?B
    E7: B?W
  39. J
    Q
    F
    b
    E
    E1
    E1: W?E
    E5: E?B
    E7: B?W
    a
    W
    J
    Q
    J
    B
    b
    E
    E5
    c
    J
    Q
    L
    B
    E7
    c
    a
    W
  40. J
    Q
    F
    b
    E1
    a
    J
    Q
    J
    b
    E5
    c
    J
    Q
    L
    E7
    c
    a
  41. M
    V
    C
    b
    E1
    a
    M
    Z
    C
    b
    E5
    c
    M
    B
    D
    E7
    c
    a
  42. M
    V
    C
    b
    a
    E1
    M
    Z
    C
    b
    E5
    c
    M
    B
    D
    E7
    P(false hit) = (1/26)length of cycle-1
    a
    c
  43. Turing’s Bombe
    NOT a computer
    Multi-Enigma Wiring
    120 rpm ? max 6 hrs to solve
    ~70% of days cracked
    Accurate crib?
    Location of crib in message?
    Find cycle in message?
    Not too many false hits?
    Crib seeding
    Fake missions – Get spotted
    18’26”N, 72’49”E = einachtzweisechsnordensiebenzweivierneunosten
    Reimann zeta zeros
  44. Agenda
    Development of Enigma Machine – Why/How/What
    The Rejewski Crack
    The Turing Crack
    Historical Impact
  45. 6 : 60,000,000
    ::
    8 : ?
  46. Secrecy
    Bletchley Park is gutted
    Enigma machines captured (and distributed!)
    Top Secret status until 1973!
  47. Marian Rejewski – During and After the War
    • 1939 – Romania
    • 1939 – France
    • French cipher bureau
    • 1940 – Algeria
    • 1940 – Back to France
    • Rozycki dies in transit
    • Underground cryptography
    • 1942 – Spain
    • Betrayed mid-crossing
    • Arrested + Jailed
    • 1942 – Portugal, Gibraltar
    • 1942 – England
    • No security clearance (Vichy France)
    • Polish Army – hand ciphers
    • 1945 – Poland
    • 1950 – Cable salesman
    • Secret Service meddling
    • 1955 – Bookkeeper
    • Until retirement
    • 1973 – Finally learns about ULTRA
    • 1980 – Dies at age 73
  48. Alan Turing –Timeline
    1936-8 – Computability, Turing Machine, Decidability, Riemann
    1939-45 – Bletchley Park
    1946 – Automatic Computing Engine
    1947-48 – Algorithms, Neural Nets, AI
    1948 – Almost an Olympian
    1948-50 – Manchester Mark I Mersenne + ??? (Was he on a secret nuclear program?? Might explain the gov’t paranoia)
    1950 – Turing Test
    1951 – Mathematical Biology
    1952 – Arrest
    1954 – Death at age 41
  49. Colossus Computer
    Cracks Lorenz cipher
    High-level German communications
    History of Computers
    Z3
    Colossus
    ENIAC
    Mark I
  50. NSA
  51. Addenda, Errata, Anecdotes
    Wiring analysis
    Hans Thilo-Schmidt
    TTTTTTTTTTTT
    Entry wheel order
    Why E1-E6, instead of E0-E5 ?
    Ring Settings and Rotor Stepping
    “Turing. Alan Turing.”
    Other WWII Cryptanalysis
    Disguising ULTRA intelligence
    Suggested Reading
    David Kahn – The Codebreakers
    Simon Singh – The Code Book

Download
Cracking the Enigma Machine - Rejewski, Turing and the Math that saved the world

 

 

Your download will begin in a moment.
If it doesn't, click here to try again.

Share Cracking the Enigma Machine - Rejewski, Turing and the Math that saved the world to:

Insert your wordpress URL:

example:

http://myblog.wordpress.com/
or
http://myblog.com/

Share Cracking the Enigma Machine - Rejewski, Turing and the Math that saved the world as:

From:

To:

Share Cracking the Enigma Machine - Rejewski, Turing and the Math that saved the world.

Enter two words as shown below. If you cannot read the words, click the refresh icon.

loading

Share Cracking the Enigma Machine - Rejewski, Turing and the Math that saved the world as:

Copy html code above and paste to your web page.

loading
PDFCast Tags | Browse | DMCA Guidelines | Terms of Use | Privacy Notice | Contact | Facebook | Valid XHTML | Sitemap | Book Sitemap
© Copyright 2011 PDFCast.org

0.0721 - 4.44MB