Algorytmy i Struktury Danych - Szyfry przestawieniowe

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.

Algorytm szyfrowania przestawieniowego ze zamianą liter w parach

Wejście:

Łańcuch tekstowy s, który zawiera tekst poddawany szyfrowaniu lub deszyfrowaniu

Wyjście:

Zaszyfrowany łańcuch s

Zmienne pomocnicze:

i

–

indeks, i ∈ N

Lista kroków:

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

Przykładowe programy

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.

C++

// 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

Wynik:

ALA MA KOCURKA BURKA I PIESKA BIESKA
LA AAMK CORUAKB RUAKI P EIKS AIBSEAK

Na początek: podrozdziału strony

W tym przypadku dla danego łańcucha s wyznaczamy taką liczbę naturalną n, aby:

n² ≤ | s |

Tekst dzielimy na grupy n znakowe. Ostatnia grupa może być niepełna – dopełniamy ją wybranymi znakami – np. znakami kropki (lub znakami liter A...Z wybieranymi pseudolosowo ). Z grup powstaje tablica. Na wyjście przesyłamy kolejne kolumny z tej tablicy (w odmianach tego szyfru kolumny mogą być permutowane ).

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 z odstępem n. Na przykład znaki w pierwszej kolumnie leżą na pozycjach 1 = 6 ( i - 1 ), w drugiej kolumnie na pozycjach 2 = 6 ( i - 1 ), itd.

Deszyfrowanie polega na ponownym wykonaniu tego samego algorytmu nad szyfrem – zatem szyfr jest symetryczny.

Algorytm szyfrowania przestawieniowego za pomocą tablicy

Wejście:

Łańcuch tekstowy s, który zawiera tekst jawny

Wyjście:

Zaszyfrowany łańcuch t

Zmienne pomocnicze:

n	–	liczba wierszy/kolumn w tablicy, n ∈ N
i, j	–	indeksy, i, j ∈ N

Lista kroków:

K01:	n ← 1	wyznaczamy n
K02:	Dopóki n² < \| s \|, wykonuj: n ← n + 1
K03:	Dopóki \| s \| < n², wykonuj: s ← s + "."	dopasowujemy długość s
K04:	t ←""	zerujemy szyfr
K05:	Dla j = 1, 2, ..., n : wykonuj krok K06	szyfrujemy
K06:	Dla i = 0, 1, ..., n - 1: wykonuj: t ← t + s [ j + n × i ]	do szyfru dołącz znak z tekstu
K07:	Zakończ

Przykładowe programy

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.

C++

// 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

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.

Na początek: podrozdziału strony

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

X₀ = 0...983

Generator ten generuje następujące liczby dla X₀ = 0:

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.

Algorytm szyfrowania przestawieniowego z pseudolosowym mieszaniem

Wejście:

s	–	łańcuch tekstowy, który zawiera tekst jawny
m, a, c	–	parametry generatora LCG, m, a, c ∈ C
X₀	–	ziarno-klucz, X₀ ∈ C

Wyjście:

Zaszyfrowany łańcuch s

Zmienne pomocnicze:

p	–	pozycja znaku, p ∈ C
i	–	indeks, i ∈ C

Lista kroków:

K01:	Dla i = 0, 1, ..., \| s \| - 1: wykonuj kroki K2...K4	przebiegamy przez kolejne znaki łańcucha s
K02:	X₀ ← ( a · X₀ + c) mod m	obliczamy kolejną liczbę pseudolosową
K03:	p ← X₀ mod \| s \|	wyznaczamy nową pozycję znaku o indeksie i
K04:	s [ i ] ↔ s [ p ]	zamieniamy znaki
K05:	Zakończ	koniec, wynik w s

Algorytm rozszyfrowywania przestawieniowego z pseudolosowym mieszaniem

Wejście:

s	–	łańcuch tekstowy, który zawiera tekst zaszyfrowany
m, a, c	–	parametry generatora LCG, m, a, c ∈ C
X₀	–	ziarno-klucz, X₀ ∈ C

Wyjście:

Rozszyfrowany łańcuch s

Zmienne pomocnicze:

p	–	pozycja znaku, p ∈ C
T	–	tablica pozycji, T ∈ C
i	–	indeks, i ∈ C

Lista kroków:

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:	X₀ ← ( a · X₀ + c) mod m	wyliczamy kolejną liczbę pseudolosową
K04:	T [ i ] ← X₀ mod \| s \|	w tablicy zapamiętujemy pozycję znaku jak przy szyfrowaniu
K05:	Dla i = \| s \| - 1, ... , 0: wykonuj: s [ i ] ↔ s [ T [ i ] ]	przebiegamy znaki łańcucha s od ostatniego do pierwszego
K06:	Zakończ	koniec, wynik w s

Przykładowe programy

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.

C++

// 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

Wynik:

127
ATAK WIECZOREM OD STRONY RZEKI
CIKYIOATAR W E ZORNKEMZESTD RO

-127
CIKYIOATAR W E ZORNKEMZESTD RO
ATAK WIECZOREM OD STRONY RZEKI

Na początek: podrozdziału strony

Szyfry przestawieniowe

Problem

Przestawianie dwóch sąsiednich liter

Algorytm szyfrowania przestawieniowego ze zamianą liter w parach

Wejście:

Wyjście:

Zmienne pomocnicze:

Lista kroków:

Przykładowe programy

Szyfr przestawieniowy z tablicą

Algorytm szyfrowania przestawieniowego za pomocą tablicy

Wejście:

Wyjście:

Zmienne pomocnicze:

Lista kroków:

Przykładowe programy

Szyfr przestawieniowy z pseudolosowym mieszaniem

Algorytm szyfrowania przestawieniowego z pseudolosowym mieszaniem

Wejście:

Wyjście:

Zmienne pomocnicze:

Lista kroków:

Algorytm rozszyfrowywania przestawieniowego z pseudolosowym mieszaniem

Wejście:

Wyjście:

Zmienne pomocnicze:

Lista kroków:

Przykładowe programy