PL188578B1

PL188578B1 - Sposób szyfrowania informacji zakodowanych binarnie

Info

Publication number: PL188578B1
Application number: PL97332675A
Authority: PL
Inventors: Alexandr Andreevich Moldovyan; Nikolay Andreevich Moldovyan; Petr Andreevich Moldovyanu
Original assignee: Alexandr Andreevich Moldovyan; Nikolay Andreevich Moldovyan; Petr Andreevich Moldovyanu
Priority date: 1997-04-02
Filing date: 1997-12-24
Publication date: 2005-02-28
Also published as: UA41481C2; EP0907269A1; CN1241352C; JP2000511755A; DE69729297D1; WO1998044678A1; ATE268080T1; DE69729297T2; US6463150B1; RU2103829C1; EP0907269B1; PL332675A1; EP0907269A4; CN1244321A

Abstract

1. Sposób szyfrowania informacji za- kodowanych binarnie, w którym formuje sie tajny klucz, tworzy sie wiecej niz jeden blok danych zawierajacy P=1 elementów binar- nego kodu informacji o ustalonej dlugosci oraz przetwarza sie te bloki danych pod kon- trola tajnego klucza, znamienny tym, ze do- datkowo generuje sie D=1 wektorów binar- nych R o ustalonej dlugosci i niezaleznych od elementów binarnego kodu informacji P, zas bloki danych R | P tworzy sie przez konkatenacje wektorów binarnych R z odpo- wiadajacymi im elementami binarnego kodu informacji P. Fig. 1 . PL PL PL PL PL PL PL PL

Description

Przedmiotem wynalazku jest sposób szyfrowania informacji zakodowanych binarnie.

W opisie właściwości sposobu będącego przedmiotem wynalazku zastosowane są następujące pojęcia:

- tajny klucz - jest informacją binarną, która jest znana tylko upoważnionemu użytkownikowi;

- szyfr - stanowi zestaw podstawowych etapów przetwarzania danych wejściowych przy użyciu tajnego klucza, który to zestaw może być realizowany przez program komputerowy, albo przez samodzielne urządzenie;

- szyfrowanie - jest to sterowany tajnym kluczem proces przetwarzania informacji cyfrowych polegający na przekształcaniu danych wyjściowych w zaszyfrowany tekst, tj. pseudolosowy ciąg znaków, z którego praktycznie nie ma możliwości odtworzenia informacji bez znajomości tajnego klucza;

- deszyfrowanie - jest to proces odwrotny do szyfrowania, umożliwiający odtworzenie informacji zgodnej z kryptogramem pod warunkiem, że operator zna klucz szyfrowania;

- wektor binarny - to pewien ciąg bitów zero jedynkowych, np. odpowiadający szumowi tłowemu lub sygnałom zakłóceń w łączu telekomunikacyjnym. W sposobie według zgłoszenia wektor binarny oznacza ciąg uporządkowanych bitów nie interpretowany w odbiorniku danych jako sygnał użytkowy lub jako informacja;

- pseudolosowe generowanie wektorów binarnych - jest to uprzednio określona zasada generowania długiego ciągu bitów według pewnego parametru początkowego i dzielenia tego ciągu na części o potrzebnej wielkości. Jako parametr początkowy można zastosować tajny klucz lub przypadkowo wybraną liczbę. Jeżeli wartość parametru początkowego nie jest znana, wówczas ciąg wyjściowy faktycznie nie będzie się odróżniał od sygnałów generowanych losowo;

- kryptoanaliza - jest to technika obliczania tajnego klucza w celu uzyskania nieupoważnionego dostępu do zaszyfrowanej informacji albo opracowanie sposobu umożliwiającego dostęp do takiej informacji bez konieczności obliczania tajnego klucza;

- odporność kryptograficzna - jest miarą niezawodności zabezpieczenia informacji i reprezentuje sobą pracochłonność mierzoną jako ilość elementarnych operacji, które należy wykonać, aby odtworzyć informację według kryptogramu przy znajomości algorytmu przekształcania, ale bez znajomości tajnego klucza.

188 578

W artykule R. Rivest: „The RC5 Encryption Algorithm, Fast Software Encryption”, Second International Workshop Proceedings (Leuven, Belgia, 14-16 grudnia 1994), Lecture Notes in Computer Science, vol. 1008, Springer Verlag, 1995, s. 86-96, ujawniony został sposób blokowego szyfrowania danych. Szyfrowanie bloków danych polega na utworzeniu tajnego klucza, a następnie podzieleniu bloku danych, który ma być przetworzony, na podbloki i kolejnym ich przetwarzaniu za pomocą operacji cyklicznego przesunięcia oraz wyznaczaniu sumy modulo-2 oraz sumy modulo-2³² aktualnego podbloku. Ta metoda blokowego szyfrowania zapewnia dużą szybkość szyfrowania w przypadku, gdy jest ona realizowana za pomocą programu komputerowego. Jednakże sposób ten nie ma wystarczającej odporności na różnicową i liniową analizę kryptograficzną, przy pomocy której atakujący ma możliwość zaszyfrowania specjalnie wybranych tekstów wyjściowych (Kaliski B. S. Yin Y.L.: „On Difeeential and Linear Cryptanalysis of the RC5 Encryption Algorithm. Advances in Cryptology” - CRYPTO'95 Proc., Spiinger Verlag, 1995, s. 171-184).

Sposób szyfrowania blokowego, ujawniony w normie DES USA National Bureau of Standards. Data Encryption Standard. Federal Information Processing Standards Publication 46, styczeń 1977, polega na tworzeniu tajnego klucza o pewnej długości, dzielenia informacji wejściowej, przedstawionej w postaci kodu binarnego, na odcinki o długości 64 bity, formowanie na ich podstawie 64-bitowych bloków danych i przetwarzanie tych bloków danych pod kontrolą tajnego klucza. Przed przetwarzaniem każdy blok danych dzieli się na dwa 32-bitowe podbloki L i R, które potem kolejno przetwarza się podczas 16 podobnych rund przetwarzania. Podczas jednej rundy przetwarzania odbywa się operacja podstawiania, permutacji i wyznaczania sumy modulo-2 w podbloku R. Każda runda kończy się przestawieniem podbloków R i L. Opisany wyżej sposób blokowego szyfrowania informacji zapewnia dużą szybkość przetwarzania w przypadku, gdy jest realizaowany za pomocą specjalistycznych obwodów elektronicznych.

Niestety sposób ten ma wadę polegającą na tym, że można w stosunku do niego skutecznie stosować kryptoanalizę w oparciu o specjalnie wybrane początkowe bloki tekstu wejściowego. Przy realizacji takiej kryptoanalizy można wybrać do szyfrowania takie początkowe teksty wejściowe, przy szyfrowaniu których występują statystyczne właściwości algorytmu szyfrowania.

Celem wynalazku jest opracowanie sposobu szyfrowania informacji zakodowanych binarnie, w którym przetwarzanie danych wejściowych byłoby realizowane w taki sposób, żeby za pomocą ustalonego tajnego klucza zapewnić przetwarzanie tekstu wyjściowego w tekst zaszyfrowany, którego struktura nie byłaby uprzednio określona. W ten sposób wykrycie statystycznych właściwości algorytmu szyfrowania jest utrudnione, co w konsekwencji zwiększa odporność na kryptoanalizę przeprowadzaną na podstawie wybranych tekstów wyjściowych.

Sposób szyfrowania informacji zakodowanych binarnie, w którym formuje się tajny klucz, tworzy się więcej niż jeden blok danych zawierający P > 1 elementów binarnego kodu informacji o ustalonej długości oraz przetwarza się te bloki danych pod kontrolą tajnego klucza, według wynalazku charakteryzuje się tym, że dodatkowo generuje się D > 1 wektorów binarnych o ustalonej długości i niezależnych od elementów binarnego kodu informacji, zaś bloki danych tworzy się przez konkatenację wektorów binarnych z odpowiadającymi im elementami binarnego kodu informacji.

Korzystnie wektory binarne generuje się w sposób przypadkowy albo pseudoprzypadkowy.

Wektory binarne poddaje się konkatenacji z odpowiadającymi im elementami binarnego kodu informacji według tajnego klucza.

Zaletą takiego rozwiązania jest to, że konfiguracja bloków zaszyfrowanego tekstu zależy nie tylko od tajnego klucza i od struktury elementów kodu informacji binarnej, ale również od struktury wektorów binarnych. Konfiguracja bloków zaszyfrowanego tekstu nie jest już z góry określona dla danego tekstu początkowego i przyjętego tajnego klucza. W konsekwencji trudniej jest odkryć właściwości statystyczne algorytmu szyfrowania, co zwiększa odporność na kryptoanalizę przeprowadzaną w oparciu o wybrane teksty źródłowe.

Losowe generowanie wektorów binarnych umożliwia otrzymanie losowej modyfikacji bloku zaszyfrowanego tekstu, co poprawia odporność na kryptoanalizę.

188 578

Pseudolosowe generowanie wektorów binarnych umożliwia realizację sposobu szyfrowania za pomocą oprogramowania komputera osobistego, bez konieczności stosowania dodatkowych układów elektronicznych do generowania liczb losowych.

Konkatenacja wektorów binarnych z odpowiadającymi im elementami binarnego kodu informacji według tajnego klucza także zwiększa odporność szyfrowania dzięki wprowadzeniu dodatkowej nieprzewidywalności w procedurach tworzenia bloków danych.

Przedmiot wynalazku, w przykładzie wykonania, jest uwidoczniony na rysunku, na którym fig. 1 przedstawia proces szyfrowania tekstu wyjściowego P, na schemacie blokowym; fig. 2 - proces deszyfracji zaszyfrowanego tekstu C, na schemacie blokowym; fig. 3 - podział binarnego kodu informacji na elementy pi, p2,..., pi, oraz zestaw wygenerowanych wektorów binarnych n, r2,..., r,; fig. 4 - blok danych wejściowych utworzony przez konkatenację elementów binarnego kodu informacji pi, P2,···, Pi z wektorami binarnymi ii, r„ zaś fig. 5 przedstawia schemat szyfrowania odnoszący się do drugiego przykładu realizacji wynalazku.

W przedstawionym na fig. 1 i 2 ogólnym schemacie kryptograficznego przetwarzania bloków danych oznaczenie RNG dotyczy generatora liczb losowych, R oznacza losowy wektor binarny, P jest elementem binarnego kodu przetwarzanej informacji, E oznacza zespół szyfrowania, D - zespół deszyfrowania, K jest tajnym kluczem, C oznacza wyjściowy tekst zaszyfrowany, zaś I jest znakiem symbolizującym operację konkatenacji.

Podczas procedury szyfrowania (fig. 1) element binarnego kodu informacji P po konkatenacji z losowo wygenerowanym wektorem binarnym R tworzy blok danych B = R | P, który dostaje się na wejście zespołu szyfrowania E wywarzającego zaszyfrowany tekst C.

Przyjmuje się, że blok wygenerowanych wektorów binarnych R stanowi część szyfru i w trakcie kryptoanalizy przeprowadzanej na bazie wybranych tekstów nie może on być zastąpiony innym przez analityka przeciwnika. Podobnie nie może być zastąpiony algorytm szyfrowania. Ten ostatni warunek jest powszechnym wymaganiem dla wszystkich znanych szyfrów. Struktura wektora binarnego R podczas procedury szyfrowania zmienia się w sposób nieprzewidywalny, ponieważ wektor jest dostarczany przez generator liczb losowych RNG. Zatem blok danych R I P przeznaczony do szyfrowania, a otrzymany po dołączeniu wektora binarnego R do elementu binarnego kodu informacji P, nie może być wcześniej znany lub wcześniej wybrany. Ten fakt stanowi podstawową trudność przy przeprowadzaniu ataku w oparciu o wybrane teksty początkowe.

Ponieważ upoważniony użytkownik zna tajny klucz K szyfrowania, może za pomocą algorytmu deszyfrowania odtworzyć strukturę wektorów binarnych R i strukturę bloku wejściowego B. Wydzielając i odrzucając wektor binarny R nie zawierający żadnej części przesyłanej informacji, upoważniony użytkownik całkowicie i jednoznacznie odtworzy przeznaczoną dla niego informację.

Podczas procedury deszyfrowania (fig. 2) zaszyfrowany tekst C podawany jest do zespołu deszyfrowania D, który odtwarza wartość bloku danych B = ,R | P za pomocą wprowadzonego tajnego klucza K. Odtworzony wektor binarny R, który był utworzony i wykorzystany w procesie szyfrowania, zostaje wymazany za pomocą operacji kolejnego sumowania modulo-2 bit po bicie wektora R i pewnej nowej losowej wielkości dostarczonej na wyjście generatora liczb losowych RNG

Generację wektorów binarnych R w sposób przypadkowy można przeprowadzać np. przez pomiar probabilistycznego procesu fizycznego lub sygnału nadajnika szumu. W wielu zastosowaniach używa się do tego celu specjalnie skonstruowane obwody elektroniczne. Zamiast generatora liczb losowych można zastosować także generator liczb pseudolosowych (np. znany z publikacji B. Schneier, „Applied Cryptography”, drugie wydanie, John Wiley & Sons, Inc., Nowy Jork, 1966, s. 416-418). Na wejście takiego generatora podaje się losowo wybraną liczbę binarną, a na jego wyjściu otrzymuje się pseudolosowy ciąg o żądanej wielkości. Wykorzystanie takiego generatora umożliwia realizację proponowanego sposobu szyfrowania za pomocą programu komputerowego, stosując jako początkową liczbę losową, np. ilość czasu upływającego pomiędzy kolejnymi uderzeniami klawiszy.

Kryptograficzne przetwarzanie podbloków może być realizowane metodą ujawnioną w opisie patentowym US 5.003.596 (M.C. Wood, „Method of Cryptographically Transforming Electronic Digital Data from One Form to Another”).

188 578

Poniżej zostały podane przykłady realizacji sposobu szyfrowania informacji zakodowanych binarnie, według wynalazku. Dla ułatwienia zrozumienia przykłady te zostały przedstawione w postaci algorytmów, które stanowią logiczną formę zapisu kolejnych procedur poszczególnych wariantów realizacji proponowanego sposobu szyfrowania blokowego.

Przykład 1 ·

Przykład ten ilustruje sposób szyfrowania informacji przedstawionych w postaci kodu binarnego podzielonego na elementy 32-bitowe. Zastosowany tu zespół szyfrowania E zapewnia przeprowadzenie szyfrowania 64-bitowych bloków danych sposobem znanym ze stanu techniki. Przykład ten jest opisany następującym algorytmem.

Algorytm 1: Szyfr blokowy 32-bitowy.

1. Wziąć kolejny 32-bitowy element kodu binarnego informacji P, utworzyć 32-bitowy wektor losowy R i uformować blok danych B = R | P, gdzie znak „|” symbolizuje konkatenację (dołączenie).

2. Stosując znany sposób szyfrowania blokowego zaszyfrować 64-bitowy blok danych.

Przykład 2

Przykład ten ilustruje sposób szyfrowania informacji przedstawionej w postaci kodu binarnego podzielonego na elementy 12-bitowe. Stosując znany sposób szyfrowania blokowego szyfruje się 64-bitowe bloki B = X | Y. Funkcja szyfrowania jest oznaczona jako E(B), to znaczy, że podczas szyfrowania blok B będzie przetwarzany zgodnie z zależnością B <— E(B), gdzie ,<--” oznacza operację przyporzaylkom-'ania. Przykład 2 jest opisany następującym algorytmem.

Algorytm 2: Szyfr blokowy 48-bitowy.

1. Uformować klucz szyfrowania.

2. Wziąć kolejne cztery 12-bitowe elementy binarnego kodu informacji pi, p₂, p3 i p4· Utworzyć w sposób pseudoprzypadkowy cztery 20-bitowe wektory binarne rą, r₂, r₃ i r.₍ oraz uformować blok danych P = pj | n | p2 | r₂ | p₃ | r₃ | p4 | r₄.

3. Podzielić ten blok danych P na dwa podbloki: P = X | Y, gdzie podblok X = p1 | ry | p2 | r2, zaś podblok Y = p₃ | r₃ I p4 | r₄.

4. Przetworzyć podblok X zgodnie z zależnością X <— E(X).

5. Nałożyć podblok X na podblok Y, zgodnie z zależnością Y <—Y © X, gdzie symbol „®” oznacza operację sumowania modulo 2.

6. Przetworzyć podblok Y zgodnie z zależnością Y <— E(Y).

7. Nałożyć podblok Y na podblok X zgodnie z zależnością X <—X © Y.

8. Przetworzyć podblok X zgodnie z zależnością X <— E(X).

9. Nałożyć podblok X na podblok Y zgodnie z zależnością Y <—Y © X.

10. Przetworzyć podblok Y zgodnie z zależnością Y <— E(Y).

11. Nałożyć podblok Y na podblok X zgodnie z zależnością X <— X © Y.

12. Wysłać blok X | Y jako blok wyjściowy zaszyfrowanego tekstu.

Przykład 2 jest zilustrowany na fig. 3-5. Na fig. 3 blok 1 jest binarnym kodem informacji podzielonym na 12 -bitowe elementy, a blok 2 reprezentuje ciąg wygenerowanych binarnych wektorów 20-bitowych. Figura 4 przedstawia strukturę uformowanych bloków danych. Schemat przetwarzania przedstawiono na fig. 5, gdzie blok E oznacza procedury szyfrowania zgodne ze znanym sposobem ze stanu techniki.

Przykład 3

Przykład ten ilustruje wykorzystanie tajnego klucza do zdefiniowania zasady formowania 1024-bajtowego bloku danych B z 32-bitowych elementów binarnego kodu informacji i 32bitowych losowych wektorów binarnych. Do procesu szyfrowania wykorzystuje się szyfr „Crab” opisany w opracowaniu B. S. Kaliskiego i M. J. Robshaw'a, Pt. „Fast Block Cipher Proposal. Fast Software Encryption” (Proceedings of the Cambridge Security Workshop,

188 578

Lecture Notes In Komputer Science, vol. 809, Springer-Verlag, 1994, s. 26-39), a także w publikacji B. Sclmeier’a, pt. „Applied Cryptography” (John Wiley & Sons, Inc., wyd. 2, Nowy Jork, 1966, s. 342-344). Szyfr ten służy do przetwarzania 1024-bajtowych bloków danych przedstawionych jako ciąg 32-bitowych podbloków Bo, B1, B₂,...., B 255 z wykorzystaniem tajnego klucza w postaci tabeli pennutacji i uporządkowanego ciągu złożonego z 2048 podkluczy Q0, Qn Q2,....,Q2047, każdy o długości 32 bity. Jako funkcję szyfrowania E przyjęto szyfr „Crab”. Przykład 3 jest opisany następującym algorytmem.

Algorytm 3: Szyfr probabilistyczny 512-bajtowy.

WEJŚCIE: 512-bajtowy element binarnego kodu informacji, przedstawiony w postaci ciągu 32-bitowych elementów binarnego kodu informacji p0, pt, p2,····, p127.

1. Uformować 128 przypadkowych 32-bitowych wektorów binarnych ro, n, n,..., r₎₂7.

2. Połączyć 32-bitowe wektory binarne i 32-bitowe elementy binarnego kodu informacji w blok pośredni (to I t1 I t2 | .... I t255), gdzie (to I t1 | t2 I .... I 1127) = (ro I r1 I ι₂ I ....I ri27 (tl28 I Ϊ129 I 130 I ..·· I t255) ⁼ (pO I p1 I p2 I I p 127)·

3. Wykorzystując podklucze Qo, Qn Q2, Q3 i Q4 obliczyć parametry u = Qo mod 256, u = Q1 mod 256, u3 = Q? mod 256, s (1) = Q3 mod 8, s(2) = Q4 mod 8.

4. Ustawić początkową wartość licznika i = O oraz utworzyć 32-bitowe zmienne bo = ! = b2 = = b255 = O.

5. Obliczyć indeks h = [(u Φ 1) ^<<<s(1) + U2] <<^<s(2)® _U3> gde.iezna„ „©” onnaczo operaęję sumowania modulo 256, wyrażenie u <<< ^s oznacza operację cyklicznego przesuwu w lewo elementu u o liczbę bitów równą wielkości s.

6. Przyporządkować zmiennej b wartość th b <— t_h.

7. Jeżeli i 255, inkrementować i <— i + 1 i przejść do punktu 5.

8. Połączyć zmienne b w 1O24-bajtowy blok danych: B = bo I b| i b₂ . .... I 2)555

9. Za pomocą szyfru „Crab” zaszyfrować blok B: C = E(B), gdzie E oznacza funkcję szyfrowania określona przez szyfr „Crab”.

WYJŚCIE: 1024-bajtowy blok zaszyfrowanego tekstu C.

Punkty 2, 3, ... 7 opisują procedurę łączenia elementów binarnego kodu informacji z wektorami binarnymi według tajnego klucza, a dokładniej w oparciu o podklucze Qo, Qn Q2, Q3, Q4Przytoczone przykłady wykazj że sposób szyfrowania blokowego można łatwo zrealizować, np. za pomocą komputerów osobistych, a opracowane w ten sposób szybkie moduły szyfrowania programowego wykazują większą odporność na ataki podejmowane przez osoby nieuprawnione, niż w przypadku szyfrowania przy pomocy wybranych tekstów pierwotnych.

Zastąpienie znanych kosztownych i skomplikowanych urządzeń szyfrujących komputerem osobistym wyposażonym w system oprogramowania szybkiego szyfrowania, zmniejsza koszty operacji szyfrowania i deszyfrowania.

188 578

Fig.3.

B»X|Y

Pi Γι Pa r₂ p3 r₃ p< r₄

Fig.4.

Y

188 578

Fig.5.

188 578

Fig. I.

ή D | B=RjP

I RNO 1—φ

Fig. 2.

Departament Wydawnictw UP RP. Nakład 50 egz. Cena 2,00 zł.

Claims

Zastrzeżenia patentowe

1. Sposób szyfrowania informacji zakodowanych binarnie, w którym formuje się tajny klucz, tworzy się więcej niż jeden blok danych zawierający P>1 elementów binarnego kodu informacji o ustalonej długości oraz przetwarza się te bloki danych pod kontrolą tajnego klucza, znamienny tym, że dodatkowo generuje się D>1 wektorów binarnych R o ustalonej długości i niezależnych od elementów binarnego kodu informacji P, zaś bloki danych ¹ r|p tworzy się przez konkatenację wektorów binarnych R z odpowiadającymi im elementami binarnego kodu informacji P.
2. Sposób według zastrz. 1, znamienny tym, że wektory binarne R generuje się w sposób przypadkowy.
3. Sposób według zastrz. 1, znamienny tym, że wektory binarne R generuje się w sposób pseudoprzypadkowy.
4. Sposób według zastrz. 1, znamienny tym, że wektory binarne R poddaje się konkatenacji z odpowiadającymi im elementami binarnego kodu informacji P według tajnego klucza K.