College Cryptografie Cursusjaar 2011 Klassieke systemen
9 februari 2011 1
Transpositie
......................................... 2
Substitutie
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14
Monoalfabetische substitutie . . . . . . . . . . . . . . . . . . . . . . . . . 22 Code . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27 Polyalfabetische substitutie
. . . . . . . . . . . . . . . . . . . . . . . . . . 31
Autoclaaf . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 37 Multiplex . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 39 One time pad . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 41
Onderwerpen
2
Kenmerken:
• • • •
permuteert de elementen van de klaartekst vorm en afmetingen transpositieblok al of niet uitvullen van het blok volgorde inschrijven en uitnemen van de tekst
• • • •
routetranspositie kolomtranspositie tweevoudige kolomtranspositie roostertranspositie
Behandelde soorten:
Transpositie
3
Bericht van president Lincoln aan generaal majoor Burnside, gedateerd Washington, November 25, 1862. BURNSIDE, Falmouth, Virginia.
BURNSIDE, Falmouth, Virginia.
Can Inn Ale me withe 2 oar our Annpas Ann me flesh ends N.V. Corn Inn out with U and Inn Heaven day nest Wed roe Moore Tom darkey hat greek a Why Hawk of Abbott Inn B chewed I if.
If I should be in a boat off Aguia Creek at dark tomorrow, Wednesday evening, could you, without inconvenience, meet me and pass an hour of two with me? A. Lincoln
Verandering leesrichting - 1
4
Bericht van president Lincoln aan generaal majoor Burnside, gedateerd Washington, November 25, 1862. BURNSIDE, Falmouth, Virginia.
BURNSIDE, Falmouth, Virginia.
Can Inn Ale me withe 2 oar our Annpas Ann me flesh ends N.V. Corn Inn out with U and Inn Heaven day nest Wed roe Moore Tom darkey hat greek a Why Hawk of Abbott Inn B chewed I if.
If I should be in a boat off Aguia Creek at dark tomorrow, Wednesday evening, could you, without inconvenience, meet me and pass an hour of two with me? A. Lincoln
Verandering leesrichting - 2
5
For Colonel Ludlow. Richardson and Brown, correspondents of the Tribune, captured at Vicksburg, are detained at Richmond. Please ascertain why they are detained and get them off if you can. The President U.S. Cryptogram guard adam them they at wayland brown for kissing venus correspondents at neptune are off nelly turning up can get why detained tribune and times richardson the are ascertain and you fills belly this if detained please odor of ludlow commissioner
Abraham Lincoln, 1 juni 1863
6
• • • •
indicator = GUARD ⇒ 5x7 tekstblok en route null willekeurig en zonder betekenis uitvuller op lege plaats codewoorden: ADAM = President U.S. NELLY = 4:30 pm NEPTUNE = Richmond ODOR = Vicksburg WAYLAND = captured VENUS = colonel
GUARD-transpositie
7
→→
stop
kissing
↓ ↓
commissioner
for
VENUS
Ludlow
Richardson
and
Brown
correspondents
of
the
Tribune
WAYLAND
at
ODOR
are
detained
at
NEPTUNE
please
ascertain
why
they
are
detained
and
get
them
off
if
you
can
ADAM
NELLY
this
fills
up
↑ ↑
turning
↑ ←← →→→
belly
↑ ↑ ↑
start
↓ →→
Indicator GUARD
←← ←← ↓ times
←← →→→
8
• • •
exotische routes: paardsprongen, magische vierkanten verschillende route voor inschrijven en voor uitnemen Sommige routes geven brokstukken leesbare tekst
Route transpositie
9
M 2
U 5
S 3
K 1
U 6
S 4
D
E
V
R
A
G
E
N
V
A
N
H
E
T
T
E
N
T
A
M
E
N
Z
Y
N
N
O
G
G
E
H
E
I
M
X
X
pt ct
DE VRAGEN VAN HET TENTAMEN ZIJN NOG GEHEIM XX RAENG MDEEA NHVVT EOIGH TYEXE NTMNE ANNZG X
Permutatie uit sleutelwoord: MUSKUS → MUS1US → 2US1US → 2U31US → 2U31U4 → 2531U4 → 253164
Kolomtranspositie
10
M 2
U 5
S 3
K 1
U 6
S 4
D
E
V
R
A
G
E
N
V
A
N
H
E
T
T
E
N
T
A
M
E
N
Z
Y
N
N
O
G
G
E
H
E
I
M
pt ct
DE VRAGEN VAN HET TENTAMEN ZIJN NOG GEHEIM RAENG MDEEA NHVVT EOIGH TYEEN TMNEA NNZG
Opsplitsing in kolommen nu onzeker: RAENGM DEEANH VVTEOI GHTYEE NTMNE ANNZG RAENGM DEEANH VVTEOI GHTYE ENTMNE ANNZG RAENG MDEEA NHVVTE OIGHTY EENTMN EANNZG
Kolomtranspositie onuitgevuld
11
A
N
A
Onregelmatig blok maakt kolomsplitsing veel moeilijker
V
L
A
O
P
P
E
A
B
R
L
H
A
R
O
U
R
D
O
J
A
P
A
N
O
R
Onregelmatig blok
Voorbeelden: Japanse K10 transpositie rond 1940 als oververcijfering van J19 code Zendia transposities
12
H 3 D O E N M
pt ct
A 1 E O N A A
R 8 N R G L D
I 4 B D E V R
N 5 R E V A I
G 2 I G A N D
T 9 E E L A
O 7 L U L A
N 6 V Z E R
L 5 E N D I A L
E 2 O D E V N A
E 3 N D V Z R
S 8 A O R E G
B 1 A E R R L
R 7 I N E L D
I 4 G M V U E
L 6 A B A L E
DEN BRIEL VOOR DE GEUZEN GEVALLEN ALVA NAAR MADRID AERRL ODEVN ANDVZ RGMVU EENDI ALABA LEINE LDAOR EG
US Army Double Transposition
13
Benaming: rooster, turning grille N
S
L
I
N
S
L
I
N
S
L
I
N
S
L
I
R
T
C
G
R
T
C
G
R
T
C
G
R
T
C
G
I
E
O
S
I
E
O
S
I
E
O
S
I
E
O
S
M
E
E
E
M
E
E
E
M
E
E
E
M
E
E
E
0◦ pt ct
90◦
180◦
270◦
SIC ERGO ELEMENTIS NSLIR TCGIE OSMEE E
Voorloper Cardano rooster in 16e eeuw: mal met uitsparingen Oudst stadhouder Willem IV 1745, laatst Duitse leger 1917
Roostergeheimschrift
14
•
• •
Monoalfabetisch letter-voor-letter: Caesar, Monoalfabeet digramsubstitutie: Playfair meervoudig: Code, Encicode gemengd: Monome - dinome, Fractionering Polyalfabetisch periodiek eenvoudig: Porta, Vigenère, Beaufort lange periode: Enigma, Hagelin meerdere alfabetten: Multiplex Polyalfabetisch aperiodiek: Autoclaaf, One time pad
Substitutie
15
• • • • • • • •
Voornamelijk gebruikt in diplomatiek verkeer Oudste voorbeelden uit plm. 1400 Mengsel van letter-, digram-, trigramsubstituties en code Klinkers krijgen meerdere vervangers (homofonen) Later krijgen ook de medeklinkers homofonen Nullen worden toegevoegd Codegroepen voor namen, plaatsen, enz. van enkele honderden tot vele duizenden Naast versies voor algemeen gebruik speciale versies voor correspondentie met bepaalde personen, zoals gezanten
Nomenclatuur
16
Philips IV (1605–1665) opvolger van Philips III in 1621 Gebeurtenissen tijdens zijn bewind:
• • • •
vrede van Munster 1648 Portugal wordt onafhankelijk verlies van koloniën aan Engeland opstanden in Catalonië en Napels
Datering: Madrid, 27 Julio 1658
Missive Philips IV
17
Don Estevan de Gamarray contreras demi ans del juerra Castellano al castillo de Gante Sire de campo general demis exitos de flandes y embaxer al estados generales de las Provincias Unidas del Pays vajo . . .
Aanhef
18
Gebeurtenis in 1658: Franse generaal Turenne verovert Duinkerken Duinkerken belangrijk blijkens:
• • • • • •
reeds genoemd in 1067 sedert 1400 vestingwerken aanvoerhaven Spaanse troepen basis voor kaapvaart tegen Nederlanders herhaaldelijk van eigenaar verwisseld mei 1940 evacuatie Engels expeditieleger
Situatie juli 1658
19
XVIe eeuw 8-11-1556 1580 18-12-1562 1582 12-7-1564 1587 6-8-1567 1585–1588 26-5-1568 16-7-1571 cifra particular: 1572 el duque de Alva 14-7-1572 etc. 21-6-1574 30-5-1575
Cifra general
XVIIe eeuw 1604 1614–1618 18-8-1647 1-10-1653 16-5-1676 1675–1689 1677–1700 26-3-1690 1691–1692 1698
20
Cifra real que aora se usa y vino á principio de Otubre del año 1653
na ne ni no nu
la le li lo lu
que que lla de de
80 81 82 83 84
J.P. Devos, Les Chiffres de Philippe II (1555–1598) Et du Despacho Universal durant le XVIIe siècle
Codeboek
21
co n si de ra do e l a p re ta do e s ta do e n que da ba n la s co sa s de Flandes co n la pe r di da de Dunquerque y suceso a d be r so . . . . . . po r la difficultad de l pa so de la ca na l de Inglaterra . . . . . .
Ontcijferde tekst
22
•
Vervanging [A–Z] ↔ π[A–Z]: k pt ct pt ct
• •
SLEUTELCONSTRUCTIEMETWOORDOFZIN SLEUTCONRIMWDFZABGHJKPQVXY DEFGHIJKLMNOPQRSTUVWXYZABC KPQVXYSLEUTCONRIMWDFZABGHJ DEFGHIJKLMNOPQRSTUVWXYZABC
TEST HFDH TEST NLJN
In theorie 26! sleutels, maar veel daarvan ct ≈ pt Frequentiedistributie van cryptogrammen is een gepermuteerde normale distributie
Monoalfabetische substitutie
23
Trinity Church, New York graf van James Leeson † 1794 REMEMBER DEATH A D G
B E H
C F I
•
Vrijmetselaars geheimschrift
K N Q
L O R
M P S
T W Z
••
U X ◦
24
V Y
•
Klassieke Caesar met k = 3, c = C k (p), p = C −k (c): pt ct
• • •
ABCDEFGHIJKLMNOPQRSTUVWXYZ CAESAR DEFGHIJKLMNOPQRSTUVWXYZABC FDHVDU
[A–Z]↔[0–25]: c = p + k mod26, p = c − k mod26 Slechts 25 sleutels (C 0 → c = p, C 1. . .C 25 → c 6= p) Frequentiedistributie van cryptogrammen is een verschoven normale distributie
Caesar substitutie
25
Digram substitutie
•
digram substitutie [AA–ZZ] → π[AA–ZZ] 676! sleutels onthouden lastig
•
Playfair Wheatstone (1854) aan de man gebracht door baron Playfair sleutels 676!
26
M T F P V
A I H Q W
G C K R X
N B L S Y
MAGNETIC
E D O U Z
M T F P V
A I H Q W
G C K R X
N B L S Y
IS → BQ
E D O U Z
M T F P V
A I H Q W
G C K R X
N B L S Y
E D O U Z
AE → GM
M T F P V
A I H Q W
G C K R X
N B L S Y
TF → FP
Verdubbelde letter: AAB. . . → AX AB . . . → GW NI . . . Meesterstukje van Alf Mongé, Signal Corps Bulletin 1936: BUFDA GNPOX IHOQY TKVQM PMBYD AAEQZ = do let author know if you succeed
Playfair
27
E D O U Z
Alfred Dreyfus wordt verdacht als de verrader in de Franse generale staf
• • • • • • • • Code
arrestatie in 1894 veroordeeld voor hoogverraad verbannen naar Duivelseiland telegram van Panizzardi, militair attaché Italië telegram in Baravelli code foutieve vertaling geheime dienst pamflet van Emile Zola „J'accuse” eerherstel pas in 1906
28
Baravelli handelscode – een deel van p.75 7500 7501 7502 7503 7504 7505 7506 7507 7508 7509
Raziocinio Razionale Razza Di buona razza Di cattiva razza (Re) Il Re di S.M. il Re Reagire, Reagente Reagito Realista, Reale
One part code
7550 7551 7552 7553 7554 7555 7556 7557 7558 7559
Reggimento Bersaglieri Reggimento Cavalleria Reggimento Linea Reggio Calabria Reggio d'Emilia Regia Regia cointeressata Regime Passato regime Sotto il regime
29
Loopgraafcode uit de Eerste Wereldoorlog About to advance Ammunition exhausted Are advancing At Attack failed Attack successful Barrage wanted Be ready to attack
Two part code
BY FB PX SX BM PF XF ZF
AF AG AP AV AW AX AZ BJ
Enemy machine gun fire Gas is being released Stretcher bearers needed Recall working party Casulties heavy Using gas shells Relief completed Situation serious
30
Optellen en aftrekken zonder carry About to advance Ammunition exhausted Are advancing At Attack failed Attack successful Barrage wanted pt ct
3256 1290 0032 9983 8971 4225 0283
Attack failed ammunition exhausted 8971 1290 onvercijferde code 4481 0925 additief 2352 1115 vercijferde code
Encicode
31
Periodieke systemen eindige sleutel herhaald gebruikt K = k 1k 2. . .k p p = periode
• • • • • •
normaal alfabet (Porta, Vigenère) teruglopend alfabet (Beaufort) gemengd alfabet in diverse varianten sleutelwoord of sleutelzin lange sleutel door progressie (Kryha, Hagelin) lange sleutel door rotor (Enigma, Sigaba)
Polyalfabetische substitutie
32
(1535–1615) in 1563 De Furtivis Literarum Notis sleutelletters AB, CD, . . . , YZ operatie [A–M] ↔ [N–Z]
Giovanni Battista Porta
Porta
33
(1523–1596) in 1563 Traicté des Chiffres „Le chiffre indéchiffrable” sleutelletters A, B, . . . , Z operatie [A–Z] ↔ [A–Z]
Blaise de Vigenère
Vigenere
34
rij boven: klaartekst rijen midden: cijfertekst linker kolom: sleutelletters Voorbeeld: KEYKEYKEYK pt KLAARTEKST ct UPYKVROOQD [A–Z] ↔ [0–25] vercijfer: C = P + K mod26 ontcijfer: P = C − K mod26
Vigenere
35
rij boven: klaar/cijfer-tekst linker kolom: sleutelletters Voorbeeld: KEYKEYKEYK pt KLAARTEKST ct ATYKNFGUGR [A–Z] ↔ [0–25] vercijfer: C = K − P mod26 ontcijfer: P = K − C mod26
Beaufort
36
US-Army cipher disk
37
Bewerkstellig aperiodiciteit door terugkoppeling
•
cijfertekst autoclaaf pt ct
•
PENTA GONKCN GDTOQOTGCD VYAND NADERT WATERLINIE KCNGD TOQOTG CDMSHZBTKH
klaartekst autoclaaf pt ct
PENTA GONVYA NDNADERTWA VYAND NADERT WATERLINIE KCNGD TOQZPT JDGEUPZGEE
Autoclaaf
38
Wheatstone
39
Jefferson (1790), Bazeries(1891), M94 (1923)
Multiplex
40
Multiplex strips
41
Oneindig lange sleutel eenmalig gebruiken sleutel + klaartext = cryptogram Voordeel: absoluut onbreekbaar Nadeel: veel sleutelmateriaal nodig Sleutelproductie: fysisch proces (radioactief verval, electronische ruis) loterij (minder goed) pseudorandomgenerator Voorbeeld: VENONA (KGB plm. 1940)
One time pad
42
