I Cifrari affine sono un caso particolare di cifrario a sostituzione. In questo tipo di cifrari la sostituzione è data da una funzione detta affine: ci=E(pi)=(k1pi+k2) mod 26 La chiave è quindi data dalle due costanti k1 e k2 Z26 La funzione di decrittazione è: pi=D(ci)=(ci-k2) k1-1 mod 26 Stelvio Cimato 1 DTI – Università di Milano, Polo di Crema ! " Se k1=7 e k2=3 la funzione di cifratura è: c=E(p)=(7p+3) mod 26 Si noti che affinchè la decifratura sia possibile deve esistere k1-1, cioè che l’equazione: La funzione di decifratura è: p=D(c)=7-1(c-3) mod 26= 15(c-3) mod 26 sia risolvibile. Quindi il testo in chiaro: la cui rappresentazione numerica é: viene cifrato in: la cui rappresentazione in stringa é: E’ possibile dimostrare che ciò è vero se e solo se: gcd(k1,26)=1 hot 7 14 19 0 23 6 axg mentre k2 può prendere qualsiasi valore tra 0 e 25 Stelvio Cimato Stelvio Cimato 2 DTI – Università di Milano, Polo di Crema # I cifrari shift e a sostituzione sono detti monoalfabetici: 3 DTI – Università di Milano, Polo di Crema $ ! % ! 1404, Pittore musicista, filosofo Proposta di usare più alfabeti cifranti e di sostituirli durante la cifratura una volta scelta la chiave ogni carattere è mappato ad un unico carattere cifrato Due approcci: Utilizzo di più alfabeti cifranti Utilizzo di cifrature di più lettere per volta A B C D E F G H I L M N O P Q R S T U V ZZ E U F A V O D N P H S G T M I L B R Z C QQ C M U N B I P L OV A T G S D R H Q F Z E Sillabe Digrammi Stelvio Cimato DTI – Università di Milano, Polo di Crema k1x=c-k2 Stelvio Cimato 4 DTI – Università di Milano, Polo di Crema Leone hbttv 5 ! & Giovanni Battista Porta, primo cifrario per digrammi [1563] Leon Battista Alberti, architetto italiano, XV secolo testo in chiaro D D II SS C CO O U B X MG testo cifrato con rotazione “AL” AL” Stelvio Cimato A B C D E F G H I J K L M N O P Q R S T U V W X Y Z A 0 26 52 78 104 130 156 182 208 234 260 286 312 338 364 390 416 442 468 494 520 546 572 598 624 650 B 1 27 53 79 105 131 157 183 209 235 261 287 313 339 365 391 417 443 469 495 521 547 573 599 625 651 C 2 28 54 80 106 132 158 184 210 236 262 288 314 340 366 392 418 444 470 496 522 548 574 600 626 652 D 3 29 55 81 107 133 159 185 211 237 263 289 315 341 367 393 419 445 471 497 523 549 575 601 627 653 E 4 30 56 82 108 134 160 186 212 238 264 290 316 342 368 394 420 446 472 498 524 550 576 602 628 654 Stelvio Cimato 6 DTI – Università di Milano, Polo di Crema F 5 31 57 83 109 135 161 187 213 239 265 291 317 343 369 395 421 447 473 499 525 551 577 603 629 655 G 6 32 58 84 110 136 162 188 214 240 266 292 318 344 370 396 422 448 474 500 526 552 578 604 630 656 H 7 33 59 85 111 137 163 189 215 241 267 293 319 345 371 397 423 449 475 501 527 553 579 605 631 657 I 8 34 60 86 112 138 164 190 216 242 268 294 320 346 372 398 424 450 476 502 528 554 580 606 632 658 J 9 35 61 87 113 139 165 191 217 243 269 295 321 347 373 399 425 451 477 503 529 555 581 607 633 659 K 10 36 62 88 114 140 166 192 218 244 270 296 322 348 374 400 426 452 478 504 530 556 582 608 634 660 L 11 37 63 89 115 141 167 193 219 245 271 297 323 349 375 401 427 453 479 505 531 557 583 609 635 661 M 12 38 64 90 116 142 168 194 220 246 272 298 324 350 376 402 428 454 480 506 532 558 584 610 636 662 N 13 39 65 91 117 143 169 195 221 247 273 299 325 351 377 403 429 455 481 507 533 559 585 611 637 663 P 15 41 67 93 119 145 171 197 223 249 275 301 327 353 379 405 431 457 483 509 535 561 587 613 639 665 Q 16 42 68 94 120 146 172 198 224 250 276 302 328 354 380 406 432 458 484 510 536 562 588 614 640 666 R 17 43 69 95 121 147 173 199 225 251 277 303 329 355 381 407 433 459 485 511 537 563 589 615 641 667 S 18 44 70 96 122 148 174 200 226 252 278 304 330 356 382 408 434 460 486 512 538 564 590 616 642 668 T 19 45 71 97 123 149 175 201 227 253 279 305 331 357 383 409 435 461 487 513 539 565 591 617 643 669 U 20 46 72 98 124 150 176 202 228 254 280 306 332 358 384 410 436 462 488 514 540 566 592 618 644 670 V 21 47 73 99 125 151 177 203 229 255 281 307 333 359 385 411 437 463 489 515 541 567 593 619 645 671 W 22 48 74 100 126 152 178 204 230 256 282 308 334 360 386 412 438 464 490 516 542 568 594 620 646 672 X 23 49 75 101 127 153 179 205 231 257 283 309 335 361 387 413 439 465 491 517 543 569 595 621 647 673 Y 24 50 76 102 128 154 180 206 232 258 284 310 336 362 388 414 440 466 492 518 544 570 596 622 648 674 Z 25 51 77 103 129 155 181 207 233 259 285 311 337 363 389 415 441 467 493 519 545 571 597 623 649 675 7 DTI – Università di Milano, Polo di Crema & testo in chiaro: testo cifrato: O 14 40 66 92 118 144 170 196 222 248 274 300 326 352 378 404 430 456 482 508 534 560 586 612 638 664 & ' Progettato da Charles Wheatstone buon amico del Barone Lyon Playfair, XIX secolo DO MA NI 92 312 346 M H K V Q Chiave: permutazione arbitraria di: numeri del cifrato lettere su righe e colonne Uso di caratteri speciali per alfabeto testo cifrato Stelvio Cimato T A F W O Z U G X S C IJ N B Y L E R D P Cifrario usato dai britannici. Anche dall’Australia durante la II guerra mondiale. M M O O C C E E LL U U H H FF P P V V N N Y Y G G Q Q W W A A B B IJ IJ S S X X R R D D K K TT ZZ Anche rettangoli 4x7, 4x8,… Stelvio Cimato 8 DTI – Università di Milano, Polo di Crema & ' M H K V Q T A F W O Z U G X S C IJ N B Y & ' L E R D P Regole: Le lettere in chiaro sono sostituite dalla lettera sulla stessa riga e colonna Le lettere ripetute vanno separate da una lettera di riempimento. Es. balloon->balxloon Le lettere sulla stessa riga vengono sostituite dalla lettere a destra Es. ar->rm Le lettere sulla stessa colonna vengono sostituite dalle lettere sottostanti Es. mu->cm testo in chiaro: DO MA NI testo cifrato: WP TH BN Stelvio Cimato DTI – Università di Milano, Polo di Crema 9 DTI – Università di Milano, Polo di Crema Stelvio Cimato 10 DTI – Università di Milano, Polo di Crema 11 & ' ( Migliore rispetto alla cifratura monoalfabetica: 26x26=676 digrammi Ma la struttura del testo rimane! Analisi condotta in base alla frequenza dei digrammi più comuni nella lingua Es. es, er, on, re, el, er, de. Inventato nel 1929 da Lester Hill. m lettere in chiaro sono sostituite con m lettere cifrate secondo m equazioni lineari Es. per m=2, (x1,x2) (y1,y2): Y1=11x1+3x2 mod 26 (y1,y2)= (x1,x2)( 11 8 ) Y2=8x1+7x2 mod 26 37 . Stelvio Cimato Stelvio Cimato 12 DTI – Università di Milano, Polo di Crema ( (y1,y2,…ym)= (x1,x2,…,xm) y=Ek(x)=xK x=Dk ( ) k1,1,k1,2,…,k1,m k2,1,k2,2,…,k2,m km,1,km,2,…,km,m ) (y)=yK-1 K-1 è l’inversa della matrice chiave KK-1=K-1K=I Stelvio Cimato ) ( ( K= 11 8 K-1= 7 18 3 7 . 23 11 Il testo in chiaro è: ciao ( ) * ) (2,8) ( 11 8 ) Y= (22+24,16+56)=(20,20) 37 . (0,14)( 11 8 ) Y= (0+42, 0+98)=(16,20) 37. Il testo cifrato è: UUQU ( ! Cifrario di Vigenère [1586] (Blaise de Vigenère, 1523-1596) ) testo in chiaro M = M0M1M2…Mn (20,20)( 7 18 ) X=(140+460,360+220)=(2,8) 23 11 X=(112+460,288+220)=(0,14) (16,20)( 7 18 ) 23 11 Il testo in chiaro è: ciao CCi ← M +K mod 26 i ← Mi i +Ki imod modt t mod 26 testo cifrato C = C0C1C2…Cn chiave K = K0K1K2…Kt-1 Testo in chiaro: CODICE MOLTO SICURO Chiave: REBUS CODIC EMOLT OSICU RO testo in chiaro REBUS REBUS REBUS RE chiave TSECU VQPFL FWJWM IS testo cifrato Stelvio Cimato DTI – Università di Milano, Polo di Crema 15 DTI – Università di Milano, Polo di Crema * K= 11 8 K-1= 7 18 3 7 . 23 11 Il testo cifrato è: UUQU ) ( Stelvio Cimato 14 DTI – Università di Milano, Polo di Crema ( 13 DTI – Università di Milano, Polo di Crema Stelvio Cimato 16 DTI – Università di Milano, Polo di Crema 17 + A B C D E F G H I J K L M N O P Q R B C D E F G H I J K L M N O P Q R S , C D E F G H I J K L M N O P Q R S T D E F G H I J K L M N O P Q R S T U E F G H I J K L M N O P Q R S T U V F G H I J K L M N O P Q R S T U V W G H H I I J J K K L L M M N N O O P P Q Q R R S S T T U U V V W W X X Y I J K L M J K L M N K LM N O L MN O P M NOP Q NOP Q R O P QR S P QR S T Q RS T U R S T U V S TU V W T UVW X U VW X Y VWX Y Z W XY ZA X Y Z A B Y ZA B C Z AB CD N O P Q R S T U V W X Y Z A B C D E O P P Q Q R R S S T T U U V V W W X X Y Y Z Z A A B B C C D D E E F F G Q R R S S T T U U V V W W X X Y Y Z Z A A B B C C D D E E F F G G H H I S T U T U V U VW V W X W X Y X Y Z Y ZA Z A B A B C B CD C D E D E F E F G F G H G HI H I J I J K J K L V W X Y Z A B C D E F G H I J K L M ! W X Y Z A B C D E F G H I J K L M N X Y Z A B C D E F G H I J K L M N O Y Z A B C D E F G H I J K L M N O P Z A B C D E F G H I J K L M N O P Q Cifrario di Vigenère [1586] (Blaise de Vigenère, 1523-1596) testo in chiaro M = M0M1M2…Mn CCi ← M +K mod 26 i ← Mi i +Ki imod modt t mod 26 testo cifrato C = C0C1C2…Cn chiave K = K0K1K2…Kt-1 Considerato inviolabile per molto tempo t Numero possibili chiavi = 26 Crittoanalisi: possibile romperlo usando indice di coincidenza ed indice mutuo di coincidenza Stelvio Cimato Stelvio Cimato 18 DTI – Università di Milano, Polo di Crema , DTI – Università di Milano, Polo di Crema 19 # Sostituzione Resiste all’analisi delle frequenze Ciascun elemento del testo viene mappato su un altro elemento Una lettera cifrata corrisponde a più simboli in chiaro Esiste un numero grande di chiavi Trasposizione Crittoanalisi: Elementi del testo in chiaro vengono scambiati di posto Si determinano le ripetizioni Dalle ripetizioni si stima la lunghezza della chiave Si analizzano le frequenze delle lettere in ognuno degli alfabeti cifranti corrispondenti alle lettere della chiave Stelvio Cimato Stelvio Cimato 20 DTI – Università di Milano, Polo di Crema DTI – Università di Milano, Polo di Crema . Scytala spartana, 500 a.C. (Plutarco in Vite La scitala è una asta di legno Il messaggio veniva scritto su una pergamena avvolta intorno all’asta Usato come cintura la striscia di pelle veniva recapitata al destinatario ..che usa la stessa scitala per ricostruire il messaggio USGEOITORGOI R NERTELUPI I NEO USGEOITORGOI RNERTELUPI I NEO MDKSJAJDIAAKJD Stelvio Cimato DTI – Università di Milano, Polo di Crema / Significa “staccionata” parallele) M A I D A I 21 Stelvio Cimato 22 DTI – Università di Milano, Polo di Crema 23 ( ) *+ , - . attackp ostpone dunti l t woamxyz ! Noto anche come Permutation Cipher: Si considerano blocchi di m caratteri Si definisce una funzione di permutazione biettiva: x: 1 2 3 4 5 6 -------------------------" # $% & ' Esempio con m=6 Alice s||crive a||... isAelc || Stelvio Cimato (x): 3 5 1 6 4 2 x: 1 2 3 4 5 6 --------------------------1(x): 361524 Stelvio Cimato 24 DTI – Università di Milano, Polo di Crema 25 DTI – Università di Milano, Polo di Crema % La vicenda inizia nel 1822 a Lynchburg, Virginia Protagonisti: Per messaggi brevi: Thomas Beale, avventuriero del selvaggio West Robert Morris, gestore di un hotel di Lynchburg Un tesoro sepolto del valore di 20 milioni di dollari Tre crittogrammi Un opuscolo pubblicato nel 1885 Poca!! Es. 3 lettere -> 6 anagrammi Per esempio prendiamo questa breve frase 35 lettere -> seimila miliardi di miliardi di miliardi 6.000.000.000.000.000.000.000.000.000.000 Stelvio Cimato Stelvio Cimato 26 DTI – Università di Milano, Polo di Crema 27 DTI – Università di Milano, Polo di Crema % % Nel 1822 Beale affidò a Morris una scatola chiusa a chiave chiedendogli di custodirla Beale non tornò mai e Morris non ricevette la chiave di decifratura Nel 1845 Morris aprì la scatola La scatola conteneva documenti cifrati Se Beale non fosse tornato entro 10 anni, Morris avrebbe dovuto aprirla All’interno c’erano tre crittogrammi e una lettera per Morris La lettera svelò che Beale aveva scoperto un giacimento d’oro I tre crittogrammi indicavano La chiave necessaria alla decifratura sarebbe stata recapitata a Morris nel 1832 l’ammontare del tesoro la sua ubicazione la ripartizione del tesoro tra gli eredi Stelvio Cimato DTI – Università di Milano, Polo di Crema Stelvio Cimato 28 DTI – Università di Milano, Polo di Crema 29 % % Morris tentò per 20 anni di decifrare i crittogrammi, senza successo Nel 1862 mostrò i crittogrammi ad un amico che, dopo aver decifrato il secondo, pubblicò un opuscolo nel 1885 Il secondo crittogramma fu decifrato usando come chiave la dichiarazione di indipendenza Stelvio Cimato DTI – Università di Milano, Polo di Crema Stelvio Cimato 30 $ 115, 73, 24, 807, 37, 52, 49, 17, 31, 62, 647, 22, 7, 15, 140, 47, 29, 107, 79, 84, 56, 239, 10, 26, 811, 5, 196, 308, 85, 52, 160, 136, 59, 211, 36, 9, 46, 316, 554, 122, 106, 95, 53, 58, 2, 42, 7, 35, 122, 53, 31, 82, 77, 250, 196, 56, 96, 118, 71, 140, 287, 28, 353, 37, 1005, 65, 147, 807, 24, 3, 8, 12, 47, 43, 59, 807, 45, 316, 101, 41, 78, 154, 1005, 122, 138, 191, 16, 77, 49, 102, 57, 72, 34, 73, 85, 35, 371, 59, 196, 81, 92, 191, 106, 273, 60, 394, 620, 270, 220, 106, 388, 287, 63, 3, 6, 191, 122, 43, 234, 400, 106, 290, 314, 47, 48, 81, 96, 26, 115, 92, 158, 191, 110, 77, 85, 197, 46, 10, 113, 140, 353, 48, 120, 106, 2, 607, 61, 420, 811, 29, 125, 14, 20, 37, 105, 28, 248, 16, 159, 7, 35, 19, 301, 125, 110, 486, 287, 98, 117, 511, 62, 51, 220, 37, 113, 140, 807, 138, 540, 8, 44, 287, 388, 117, 18, 79, 344, 34, 20, 59, 511, 548, 107, 603, 220, 7, 66, 154, 41, 20, 50, 6, 575, 122, 154, 248, 110, 61, 52, 33, 30, 5, 38, 8, 14, 84, 57, 540, 217, 115, 71, 29, 84, 63, 43, 131, 29, 138, 47, 73, 239, 540, 52, 53, 79, 118, 51, 44, 63, 196, 12, 239, 112, 3, 49, 79, 353, 105, 56, 371, 557, 211, 505, 125, 360, 133, 143, 101, 15, 284, 540, 252, 14, 205, 140, 344, 26, 811, 138, 115, 48, 73, 34, 205, 316, 607, 63, 220, 7, 52, 150, 44, 52, 16, 40, 37, 158, 807, 37, 121, 12, 95, 10, 15, 35, 12, 131, 62, 115, 102, 807, 49, 53, 135, 138, 30, 31, 62, 67, 41, 85, 63, 10, 106, 807, 138, 8, 113, 20, 32, 33, 37, 353, 287, 140, 47, 85, 50, 37, 49, 47, 64, 6, 7, 71, 33, 4, 43, 47, 63, 1, 27, 600, 208, 230, 15, 191, 246, 85, 94, 511, 2, 270, 20, 39, 7, 33, 44, 22, 40, 7, 10, 3, 811, 106, 44, 486, 230, 353, 211, 200, 31, 10, 38, 140, 297, 61, 603, 320, 302, 666, 287, 2, 44, 33, 32, 511, 548, 10, 6, 250, 557, 246, 53, 37, 52, 83, 47, 320, 38, 33, 807, 7, 44, 30, 31, 250, 10, 15, 35, 106, 160, 113, 31, 102, 406, 230, 540, 320, 29, 66, 33, 101, 807, 138, 301, 316, 353, 320, 220, 37, 52, 28, 540, 320, 33, 8, 48, 107, 50, 811, 7, 2, 113, 73, 16, 125, 11, 110, 67, 102, 807, 33, 59, 81, 158, 38, 43, 581, 138, 19, 85, 400, 38, 43, 77, 14, 27, 8, 47, 138, 63, 140, 44, 35, 22, 177, 106, 250, 314, 217, 2, 10, 7, 1005, 4, 20, 25, 44, 48… Stelvio Cimato DTI – Università di Milano, Polo di Crema 31 DTI – Università di Milano, Polo di Crema " DECLARATION OF INDEPENDENCE When(1) in(2) the(3) course(4) of(5) human(6) events(7) it(8) becomes(9) necessary(10) for(11) one(12) people(13) to(14) dissolve(15) the(16) political(17) bands(18) which(19) have(20) connected(21) them(22) with(23) another(24) and(25) to(26) assume(27) among(28) the(29) powers(30) of(31) the(32) earth(33) the(34) separate(35) and(36) equal(37) station(38) to(39) which(40) the(41) laws(42) of(43) nature(44) and(45) of(46) nature' s(47) god(48) entitle(49) them(50) a(51) decent(52) respect(53) to(54) the(55) opinions(56) of(57) mankind(58) requires(59) that(60) they(61) should(62) declare(63) the(64) causes(65) which(66) impel(67) them(68) to(69) the(70) separation(71) we(72) hold(73) these(74) truths(75) to(76) be(77) self(78) evident(79) that(80) all(81) men(82) are(83) created(84) equal(85) that(86) they(87) are(88) endowed(89) by(90) their(91) creator(92) with(93) certain(94) unalienable(95) rights(96) that(97) among(98) these(99) are(100) life(101) liberty(102) and(103) the(104) pursuit(105) of(106) happiness(107) that(108) to(109) secure(110) these(111) rights(112) governments(113) are(114) instituted(115) among(116) men(117) … Stelvio Cimato 32 33 DTI – Università di Milano, Polo di Crema % Il primo e il terzo crittogramma di Beale sono inviolati da più di un secolo " I have deposited in the county of Bedford, (Virginia) about four miles from Buford, in an excavation or vault, six feet below the surface of the ground, the following articles belonging jointly to the parties whose names are given in number three herewith. The first deposit consisted of ten hundred and fourteen pounds of gold and thirty eight hundred and twelve pounds of silver deposited Nov. Eighteen Nineteen. The second was made Dec. Eighteen Twenty one and consisted of nineteen hundred and eighty eight of silver, also jewels obtained in St. Louis in exchange to save transportation and valued at thirteen thousand dollars. The above is securely packed in iron pots with iron covers the vault is roughly lined with stone and the vessels rest on solid stone and are covered with others. Paper number one describes the exact locality of the vault so that no difficulty will be had in finding it." I crittogrammi potrebbero essere stati alterati dall’autore dell’opuscolo per impedirne la decifratura E il tesoro? Qualcuno potrebbe averlo trovato utilizzando gli indizi dell’unico crittogramma decifrato L’intera storia potrebbe essere una montatura, ispirata dal romanzo di Edgar Allan Poe Ancora oggi crittoanalisti e cacciatori di tesori sono affascinati dalla vicenda Stelvio Cimato DTI – Università di Milano, Polo di Crema Stelvio Cimato 34 DTI – Università di Milano, Polo di Crema 35