Serwis Edukacyjny w I-LO w Tarnowie Materiały dla uczniów liceum |
Wyjście Spis treści Wstecz Dalej Autor artykułu: mgr Jerzy Wałaszek |
©2024 mgr Jerzy Wałaszek |
ProblemNależy opracować algorytm szyfrujący i deszyfrujący za pomocą szyfru przestawieniowego Szyfr przestawieniowy (ang. transposition cifer) polega na zamianie położenia znaków tworzących tekst, przez co wiadomość staje się nieczytelna dla niewtajemniczonego odbiorcy. W zaszyfrowanym tekście znajdują się wszystkie znaki tekstu jawnego. Zaczniemy od najprostszych szyfrów przestawieniowych. |
W tym rodzaju szyfru tekst dzielimy na pary znaków. Następnie w każdej parze zamieniamy ze sobą litery,
Przykład:
tekst = ALA MA KOCURKA BURKA I PIESKA BIESKA
pary = AL A MA K OC UR KA B UR KA I P IE SK A BI ES KA zamiana = LA A AM K CO RU AK B RU AK I P EI KS A IB SE AK szyfr = LA AAMK CORUAKB RUAKI P EIKS AIBSEAK
|
Tekst da się podzielić na pary, jeśli zawiera parzystą liczbę znaków. W przeciwnym razie ostatnia para jest niepełna. W takiej niepełnej parze liter oczywiście nie zamieniamy miejscami. Zwróć uwagę, iż ten szyfr jest symetryczny. Jeśli poddamy szyfrowaniu tekst poprzednio zaszyfrowany, to otrzymamy z powrotem tekst jawny.
K01: i ← 0 ; rozpoczynamy od pierwszego znaku K02: Dopóki i+1 < |s|, wykonuj kroki K03…K04 K03: s[i] ↔ s[i+1] ; zamieniamy znaki w parze K04: i ← i+2 ; przesuwamy się do następnej pary znaków K05: Zakończ
Uwaga: Zanim uruchomisz program, przeczytaj wstęp do tego artykułu, w którym wyjaśniamy funkcje tych programów oraz sposób korzystania z nich. |
Program wczytuje wiersz tekstu, szyfruje go przez zamianę liter w parach i wyświetla wynik. |
Pascal// Szyfr przestawieniowy // Data: 11.02.2011 // (C)2020 mgr Jerzy Wałaszek //----------------------------- program cifer; var s : string; x : char; i : integer; begin // odczytujemy tekst readln(s); // zamieniamy miejscami litery i := 1; while i < length(s) do begin x := s[i]; s[i] := s[i+1]; s[i+1] := x; inc(i, 2); end; // wyświetlamy wynik writeln(s); end. |
// Szyfr przestawieniowy // Data: 11.02.2011 // (C)2020 mgr Jerzy Wałaszek //----------------------------- #include <iostream> #include <string> using namespace std; int main() { string s; unsigned i; // odczytujemy tekst getline(cin, s); // zamieniamy miejscami litery for(i = 0; i < s.length()-1; i+=2) swap(s[i], s[i+1]); // wyświetlamy wynik cout << s << endl; return 0; } |
Basic' Szyfr przestawieniowy ' Data: 11.02.2011 ' (C)2020 mgr Jerzy Wałaszek '----------------------------- Dim As String s, x Dim As Integer i ' odczytujemy tekst Line Input s ' zamieniamy miejscami litery For i = 1 To Len(s)-1 Step 2 x = Mid(s, i, 1) Mid(s, i, 1) = Mid(s, i+1, 1) Mid(s, i+1, 1) = x Next ' wyświetlamy wynik Print s End |
Python
(dodatek)# Szyfr przestawieniowy # Data: 27.03.2024 # (C)2024 mgr Jerzy Wałaszek #--------------------------- # odczytujemy tekst s = input() # zamieniamy miejscami litery for i in range(0, len(s)-1, 2): s = s[:i]+s[i+1]+s[i]+s[i+2:] # wyświetlamy wynik print(s) |
Wynik: |
ALA MA KOCURKA BURKA I PIESKA BIESKA LA AAMK CORUAKB RUAKI P EIKS AIBSEAK |
W tym przypadku dla danego łańcucha s wyznaczamy taką liczbę
n2 ≤ |s|
Tekst dzielimy
tekst = KUBUŚ PUCHATEK NIE MIAŁ DZIŚ MIODKU – 35 znaków, n = 6 grupy = KUBUŚ PUCHAT EK NIE MIAŁ DZIŚ M IODKU# tablica = KUBUŚ PUCHAT EK NIE MIAŁ DZIŚ M IODKU. kolumny = KPE DI UUKMZO BC IID UHNAŚK ŚAIŁ U TE M. szyfr = KPE DIUUKMZOBC IIDUHNAŚKŚAIŁ U TE M.
|
W rzeczywistości tablicy nie musimy wcale tworzyć. Kolejne kolumny uzyskamy
odczytując znaki
Deszyfrowanie polega na ponownym wykonaniu tego samego algorytmu nad szyfrem – zatem szyfr jest symetryczny.
K01: n ← 1 ; wyznaczamy n K02: Dopóki n2 < |s|, wykonuj: n ← n+1 K03: Dopóki |s| < n2, ; dopasowujemy długość s wykonuj: s ← s+"." K04: t ←"" ; zerujemy szyfr K05: Dla j = 1, 2, …, n: ; szyfrujemy/deszyfrujemy wykonuj krok K06 K06: Dla i = 0, 1, …, n-1: ; do szyfru dołącz znak z tekstu wykonuj: t ← t+s[j+n×i] K07: Zakończ zwracając t
Uwaga: Zanim uruchomisz program, przeczytaj wstęp do tego artykułu, w którym wyjaśniamy funkcje tych programów oraz sposób korzystania z nich. |
Program odczytuje łańcuch znaków, które szyfruje/rozszyfrowuje. |
Pascal// Szyfr przestawieniowy // Data: 12.02.2011 // (C)2020 mgr Jerzy Wałaszek //----------------------------- program cifer; var s, t : string; n, i, j : integer; begin // odczytujemy tekst/szyfr readln(s); // dopasowujemy n n := 1; while n*n < length(s) do inc(n); // dopasowujemy s while length(s) < n*n do s := s+'.'; // szyfrujemy/deszyfrujemy t := ''; for j := 1 to n do for i := 0 to n-1 do t := t+s[j+n*i]; // wypisujemy wynik writeln(t); end. |
// Szyfr przestawieniowy // Data: 12.02.2011 // (C)2020 mgr Jerzy Wałaszek //----------------------------- #include <iostream> #include <string> using namespace std; int main() { string s, t; unsigned n, i, j; // odczytujemy tekst/szyfr getline(cin, s); // dopasowujemy n for(n = 1; n*n < s.length(); n++); // dopasowujemy s while(s.length() < n*n) s += "."; // szyfrujemy/deszyfrujemy t = ""; for(j = 0; j < n; j++) for(i = 0; i < n; i++) t += s[j+n*i]; // wypisujemy wynik cout << t << endl; return 0; } |
Basic' Szyfr przestawieniowy ' Data: 12.02.2011 ' (C)2020 mgr Jerzy Wałaszek '----------------------------- Dim As String s, t Dim As Integer n, i, j ' odczytujemy tekst/szyfr Line Input s ' dopasowujemy n n = 1 While n*n < Len(s) n += 1 Wend ' dopasowujemy s While Len(s) < n*n s += "." Wend ' szyfrujemy/deszyfrujemy t = "" For j = 1 To n For i = 0 To n-1 t += Mid(s, j+n*i, 1) Next Next ' wypisujemy wynik Print t End |
Python
(dodatek)# Szyfr przestawieniowy # Data: 28.03.2024 # (C)2024 mgr Jerzy Wałaszek #----------------------------- # odczytujemy tekst/szyfr s = input() # dopasowujemy n n = 1 while n*n < len(s): n += 1 # dopasowujemy s while len(s) < n*n: s += "." # szyfrujemy/deszyfrujemy t = "" for j in range(n): for i in range(n): t += s[j+n*i] # wypisujemy wynik print(t) print() |
Wynik: |
KUBUŚ PUCHATEK NIE MIAŁ DZIŚ MIODKU. KPE DIUUKMZOBC IIDUHNAŚKŚAIŁ U TE M. KPE DIUUKMZOBC IIDUHNAŚKŚAIŁ U TE M. KUBUŚ PUCHATEK NIE MIAŁ DZIŚ MIODKU. |
Tworzymy własny generator pseudolosowy, który posłuży nam do generowania pozycji znaków. Kluczem będzie ziarno tego generatora. Następnie dla kolejnych znaków szyfrowanego tekstu wyznaczamy liczbę pseudolosową, która będzie nową pozycją tego znaku w tekście. Pozycja ta musi być w zakresie od 1 do |s|. Po wyznaczeniu nowej pozycji zamieniamy ze sobą znak bieżący ze znakiem na pseudolosowej pozycji.
Rozszyfrowywanie wymaga wykonania operacji w kolejności odwrotnej do szyfrowania. Zatem po wczytaniu szyfru, wyznaczamy w osobnej tablicy pseudolosowe pozycje znaków identycznie jak przy szyfrowaniu. Następnie pozycje te odczytujemy od końca i wymieniamy znaki od tyłu szyfru cofając się do początku. W ten sposób usuniemy wymiany znaków wprowadzone w trakcie szyfrowania.
Na potrzeby naszego artykułu wybierzmy generator pseudolosowy o następujących parametrach (w rzeczywistych zastosowaniach moduł powinien być bardzo duży – szczególnie, gdy szyfrowane są długie łańcuchy znakowe):
m = 984 = 2×2×2×3×41
a = 493 = 2×2×3×41+1
c = 385 = 5×7×11
X0 = 0…983
Generator ten generuje następujące liczby
385 278 663 556 941 834 235 128 513 406 791 684 85 962
363 256 641 534 919 812 213 106 491 384 769 662 63 940 341 234 619
512 897 790 191 84 469 362 747 640 41 918 319 212 597 490 875 768
169 62 447 340 725 618 19 896 297 190 575 468 853 746 147 40 425 318
703 596 981 874 275 168 553 446 831 724 125 18 403 296 681 574 959
852 253 146 531 424 809 702 103 980 381 274 659 552 937 830 231 124
509 402 787 680 81 958 359 252 637 530 915 808 209 102 487 380 765
658 59 936 337 230 615 508 893 786 187 80 465 358 743 636 37 914 315
208 593 486 871 764 165 58 443 336 721 614 15 892 293 186 571 464
849 742 143 36 421 314 699 592 977 870 271 164 549 442 827 720 121
14 399 292 677 570 955 848 249 142 527 420 805 698 99 976 377 270
655 548 933 826 227 120 505 398 783 676 77 954 355 248 633 526 911
804 205 98 483 376 761 654 55 932 333 226 611 504 889 782 183 76 461
354 739 632 33 910 311 204 589 482 867 760 161 54 439 332 717 610 11
888 289 182 567 460 845 738 139 32 417 310 695 588 973 866 267 160
545 438 823 716 117 10 395 288 673 566 951 844 245 138 523 416 801
694 95 972 373 266 651 544 929 822 223 116 501 394 779 672 73 950
351 244 629 522 907 800 201 94 479 372 757 650 51 928 329 222 607
500 885 778 179 72 457 350 735 628 29 906 307 200 585 478 863 756
157 50 435 328 713 606 7 884 285 178 563 456 841 734 135 28 413 306
691 584 969 862 263 156 541 434 819 712 113 6 391 284 669 562 947
840 241 134 519 412 797 690 91 968 369 262 647 540 925 818 219 112
497 390 775 668 69 946 347 240 625 518 903 796 197 90 475 368 753
646 47 924 325 218 603 496 881 774 175 68 453 346 731 624 25 902 303
196 581 474 859 752 153 46 431 324 709 602 3 880 281 174 559 452 837
730 131 24 409 302 687 580 965 858 259 152 537 430 815 708 109 2 387
280 665 558 943 836 237 130 515 408 793 686 87 964 365 258 643 536
921 814 215 108 493 386 771 664 65 942 343 236 621 514 899 792 193
86 471 364 749 642 43 920 321 214 599 492 877 770 171 64 449 342 727
620 21 898 299 192 577 470 855 748 149 42 427 320 705 598 983 876
277 170 555 448 833 726 127 20 405 298 683 576 961 854 255 148 533
426 811 704 105 982 383 276 661 554 939 832 233 126 511 404 789 682
83 960 361 254 639 532 917 810 211 104 489 382 767 660 61 938 339
232 617 510 895 788 189 82 467 360 745 638 39 916 317 210 595 488
873 766 167 60 445 338 723 616 17 894 295 188 573 466 851 744 145 38
423 316 701 594 979 872 273 166 551 444 829 722 123 16 401 294 679
572 957 850 251 144 529 422 807 700 101 978 379 272 657 550 935 828
229 122 507 400 785 678 79 956 357 250 635 528 913 806 207 100 485
378 763 656 57 934 335 228 613 506 891 784 185 78 463 356 741 634 35
912 313 206 591 484 869 762 163 56 441 334 719 612 13 890 291 184
569 462 847 740 141 34 419 312 697 590 975 868 269 162 547 440 825
718 119 12 397 290 675 568 953 846 247 140 525 418 803 696 97 974
375 268 653 546 931 824 225 118 503 396 781 674 75 952 353 246 631
524 909 802 203 96 481 374 759 652 53 930 331 224 609 502 887 780
181 74 459 352 737 630 31 908 309 202 587 480 865 758 159 52 437 330
715 608 9 886 287 180 565 458 843 736 137 30 415 308 693 586 971 864
265 158 543 436 821 714 115 8 393 286 671 564 949 842 243 136 521
414 799 692 93 970 371 264 649 542 927 820 221 114 499 392 777 670
71 948 349 242 627 520 905 798 199 92 477 370 755 648 49 926 327 220
605 498 883 776 177 70 455 348 733 626 27 904 305 198 583 476 861
754 155 48 433 326 711 604 5 882 283 176 561 454 839 732 133 26 411
304 689 582 967 860 261 154 539 432 817 710 111 4 389 282 667 560
945 838 239 132 517 410 795 688 89 966 367 260 645 538 923 816 217
110 495 388 773 666 67 944 345 238 623 516 901 794 195 88 473 366
751 644 45 922 323 216 601 494 879 772 173 66 451 344 729 622 23 900
301 194 579 472 857 750 151 44 429 322 707 600 1 878 279 172 557 450
835 728 129 22 407 300 685 578 963 856 257 150 535 428 813 706 107 0 |
W algorytmie będą zaszyte wartości współczynników tego generatora.
K01: Dla i = 0, 1, …, |s|-1: ; przebiegamy przez kolejne wykonuj kroki K2…K4 ; znaki łańcucha s K02: X0 ← (a×X0+c) mod m ; obliczamy kolejną liczbę ; pseudolosową K03: p ← X0 mod |s| ; wyznaczamy nową pozycję znaku ; o indeksie i K04: s[i] ↔ s[p] ; zamieniamy znaki K05: Zakończ ; koniec, wynik w s
K01: Utwórz tablicę T o rozmiarze |s| ; tworzymy tablicę na indeksy ; znaków K02: Dla i = 0, 1, …, |s|-1: wykonuj kroki K03…K04 K03: X0 ← (a×X0+c) mod m ; wyliczamy kolejną liczbę pseudolosową K04: T[i] ← X0 mod |s| ; w tablicy zapamiętujemy pozycję znaku ; jak przy szyfrowaniu K05: Dla i = |s|-1, … , 0: ; przebiegamy znaki łańcucha s wykonuj: s[i] ↔ s[T[i]] ; od ostatniego do pierwszego ; i zamieniamy je ze znakami na pozycjach T[i] K06: Zakończ ; koniec, wynik w s
Uwaga: Zanim uruchomisz program, przeczytaj wstęp do tego artykułu, w którym wyjaśniamy funkcje tych programów oraz sposób korzystania z nich. |
Program odczytuje klucz szyfrujący oraz tekst. Jeśli klucz ma wartość dodatnią, to tekst jest szyfrowany. Jeśli klucz ma wartość ujemną, to tekst zostaje rozszyfrowany. |
Pascal// Szyfr przestawieniowy // Data: 12.02.2011 // (C)2020 mgr Jerzy Wałaszek //----------------------------- program cifer; var s : string; i, m, a, c, X0, p : integer; x : char; T : array of integer; begin // odczytujemy klucz readln(X0); // odczytujemy tekst/szyfr readln(s); // definiujemy generator pseudolosowy m := 984; a := 493; c := 385; // jeśli klucz > 0, to szyfrujemy, // inaczej rozszyfrowujemy if X0 > 0 then // przestawiamy znaki tekstu for i := 1 to length(s) do begin // wyznaczamy nową pozycję znaku X0 := (a*X0+c) mod m; p := 1+X0 mod length(s); // wymieniamy znaki x := s[i]; s[i] := s[p]; s[p] := x; end else begin // odtwarzamy klucz X0 := -X0; // tworzymy tablicę dynamiczną na pozycje SetLength(T, length(s)); // wyliczamy pozycje jak przy szyfrowaniu for i := 0 to length(s)-1 do begin X0 := (a*X0+c) mod m; T[i] := 1+X0 mod length(s); end; // wykorzystujemy pozycje od końca szyfru for i := length(s) downto 1 do begin p := T[i-1]; x := s[i]; s[i] := s[p]; s[p] := x; end; // usuwamy tablicę dynamiczną SetLength(T, 0); end; // wypisujemy wynik writeln(s); end. |
// Szyfr przestawieniowy // Data: 19.02.2011 // (C)2020 mgr Jerzy Wałaszek //----------------------------- #include <iostream> using namespace std; int main() { string s; int i, m, a, c, X0, *T; // odczytujemy klucz cin >> X0; // odczytujemy tekst/szyfr cin.ignore(255, '\n'); getline(cin, s); // definiujemy generator pseudolosowy m = 984; a = 493; c = 385; // jeśli klucz > 0, to szyfrujemy // inaczej rozszyfrowujemy if(X0 > 0) // przestawiamy znaki tekstu for(i = 0; i < (int)s.length(); i++) { // wyznaczamy nową pozycję znaku X0 = (a*X0+c)%m; // wymieniamy znaki swap(s[i], s[X0%s.length()]); } else { // odtwarzamy klucz X0 = -X0; // tworzymy tablicę dynamiczną na pozycje T = new int[s.length()]; // wyliczamy pozycje jak przy szyfrowaniu for(i = 0; i < (int)s.length(); i++) { X0 = (a*X0+c)%m; T[i] = X0%s.length(); } // wykorzystujemy pozycje od końca szyfru for(i = s.length()-1; i >= 0; i--) { swap(s[i], s[T[i]]); } // usuwamy tablicę dynamiczną delete [] T; } // wypisujemy wynik cout << s << endl; return 0; } |
Basic' Szyfr przestawieniowy ' Data 19.02.2011 ' (C)2020 mgr Jerzy Wałaszek '----------------------------- Dim As String s, x Dim As Integer i, m, a, c, X0, p ' odczytujemy klucz Input X0 ' odczytujemy tekst/szyfr Line Input s ' definiujemy generator pseudolosowy m = 984 a = 493 c = 385 ' jeśli klucz > 0, to szyfrujemy ' inaczej rozszyfrowujemy If X0 > 0 Then ' przestawiamy znaki tekstu For i = 1 To Len(s) ' wyznaczamy nową pozycję znaku X0 = (a*X0+c) Mod m p = 1+X0 Mod Len(s) ' wymieniamy znaki x = Mid(s, i, 1) Mid(s, i, 1) = Mid(s, p, 1) Mid(s, p, 1) = x Next Else ' odtwarzamy klucz X0 = -X0 ' tworzymy tablicę dynamiczną na pozycje Dim As Integer T(Len(s)) ' wyliczamy pozycje jak przy szyfrowaniu For i = 1 To Len(s) X0 = (a*X0+c) Mod m T(i) = 1+X0 Mod Len(s) Next ' wykorzystujemy pozycje od końca szyfru For i = Len(s) To 1 Step -1 p = T(i) x = Mid(s, i, 1) Mid(s, i, 1) = Mid(s, p, 1) Mid(s, p, 1) = x Next End If ' wypisujemy wynik Print s End |
Python
(dodatek)# Szyfr przestawieniowy # Data: 28.02.2024 # (C)2024 mgr Jerzy Wałaszek #----------------------------- # odczytujemy klucz x0 = int(input()) # odczytujemy tekst/szyfr s = input() # definiujemy generator pseudolosowy m = 984 a = 493 c = 385 # jeśli klucz > 0, to szyfrujemy # inaczej rozszyfrowujemy if x0 > 0: # przestawiamy znaki tekstu for i in range(len(s)): # wyznaczamy nową pozycję znaku x0 = (a * x0 + c) % m # wymieniamy znaki s1 = s[i] j = x0 % len(s) s2 = s[j] s = s[:i]+s2+s[i+1:] s = s[:j]+s1+s[j+1:] else: # odtwarzamy klucz x0 = -x0 # tworzymy tablicę dynamiczną na pozycje t = [] for i in range(len(s)): # wyliczamy pozycje jak przy szyfrowaniu x0 = (a * x0 + c) % m t.append(x0 % len(s)) # wykorzystujemy pozycje od końca szyfru for i in reversed(range(len(s))): s1 = s[i] j = t[i] s2 = s[j] s = s[:i]+s2+s[i+1:] s = s[:j]+s1+s[j+1:] # usuwamy tablicę dynamiczną t = [] # wypisujemy wynik print(s) print() |
Wynik: |
127 ATAK WIECZOREM OD STRONY RZEKI CIKYIOATAR W E ZORNKEMZESTD RO -127 CIKYIOATAR W E ZORNKEMZESTD RO ATAK WIECZOREM OD STRONY RZEKI |
Zespół Przedmiotowy Chemii-Fizyki-Informatyki w I Liceum Ogólnokształcącym im. Kazimierza Brodzińskiego w Tarnowie ul. Piłsudskiego 4 ©2024 mgr Jerzy Wałaszek |
Materiały tylko do użytku dydaktycznego. Ich kopiowanie i powielanie jest dozwolone
pod warunkiem podania źródła oraz niepobierania za to pieniędzy.
Pytania proszę przesyłać na adres email:
Serwis wykorzystuje pliki cookies. Jeśli nie chcesz ich otrzymywać, zablokuj je w swojej przeglądarce.
Informacje dodatkowe.