Sesiunea internaţională de comunicări ştiinţifice “MATEMATICA DE IERI SI DE AZI”,

cu tema “Modele matematice în ştiinţă, tehnică şi artă”

4 aprilie

2012

Matematica de ieri si de azi = ISSN 1844 – 7821

ISSN-L = 1844 – 7821

LUCRĂRILE CADRELOR DIDACTICE

1. “ALGORITMI GENETICI SI EVOLUTIVI”

Profesor: Alina-Gabriela BOCA, specialitatea Informatica, Colegiul National” Ion Neculce”, sector 6, Bucureşti

2. “APLICAŢII ALE FORMULEI LUI EULER” Profesor: Diana MIHALCEA, specialitatea Matematică, Colegiul Tehnic de Posta si Telecomunicatii ,,Gh. Airinei", sector 6, Bucureşti.

3. “APLICAŢII ALE TEOREMELOR LUI EULER, FERMAT ŞI WILSON ÎN TEORIA NUMERELOR”

Profesor: Mariana PĂTRAŞCU, specialitatea Matematică, Şcoala Nr. 24 " Sf. Gheorghe" Craiova, judeţul Dolj.

4. “ASUPRA UNEI PROBLEME DE LOC GEOMETRIC” Profesor: Ileana GIUBELAN, specialitatea Matematică, Şcoala Nr. 24 " Sf. Gheorghe" Craiova, judeţul Dolj.

5. “APLICATII GRAFICE IN MAPLE” Profesor: Adrian FLOREA, specialitatea Matematică, Şcoala Nr. 98 ,,Avram Iancu", sector 4, Bucureşti.

6. “APLICATII ALE TRIGONOMETRIEI IN STIINTA SI TEHNICA” Profesor: Maria GHIBAN, specialitatea Matematică, Colegiul Tehnic “Traian”, sector 2, Bucureşti.

7. “APLICATII IN ECONOMIE ALE EXTREMELOR LOCALE ALE FUNCTIILOR DE MAI MULTE VARIABILE”

Profesor: Adina Florenta GIUCLEA, specialitatea Matematică, Colegiul Tehnic “Dimitrie Leonida”, sector 2, Bucureşti.

8. “APLICAREA METODEI PROIECTULUI EDUCAŢIONAL ÎN ARIA CURRICULARĂ MATEMATICĂ ŞI ŞTIINŢE”

Profesor: Maria-Melania MICUŢ, specialitatea Matematică, Colegiul Tehnic "Carol I", sector 6, Bucureşti.

9. “APLICAŢII ALE ANALIZEI MATEMATICE ÎN GEOMETRIE” Profesor: Lidia ANGELESCU, specialitatea Matematică, Colegiul Tehnic “Traian”, sector 2, Bucureşti.

10. “APLICAŢIA GEOGEBRA ÎN LECŢIILE DE MATEMATICĂ” Profesor: Elena POPESCU, specialitatea Matematică, Colegiul Tehnic de Aeronautică “Henri Coandă”, sector 1, Bucureşti.

NUMERELE IRAŢIONALE ŞI SECRETUL PERFECT

Neagoe Mihai Cătălin, profesor

Şcoala Numărul 182, Bucureşti

Abstract: This article approaches the possibility of the use of irrational numbers in cryptography. The

set of all irrational numbers has infinitely many elements. Sometimes, an irrational number can be

expressed through a symbol or a finite string of symbols, although the irrational number itself contains

an infinite number of decimals that can carry a nearly limitless quantity of information. Furthermore,

based on same properties of these numbers, we can obtain stream ciphers which fulfill the perfect

secrecy (Shannon) property.

Introducere Istoria mesajelor ascunse este veche şi fascinantă. Ea începe cu semnele şi simbolurile

ezoterice preistorice cu caracter magico-religios şi după o evoluţie de mii de ani continuă cu metode sofisticate de criptare-decriptare şi criptanaliză, grupate în ştiinţa criptografiei.

Primele texte cifrate sunt cunoscute din antichitate. Astfel, istoricul roman Gaius Suetonius Tranquillus (cca. 69–130), menţionează în De Vita Caesarum cum Iulius Cezar folosea scrierea cifrată: ,,Există scrisori ale lui (Cesar – na) către Cicero, precum şi pentru apropiaţii lui în treburi private, şi în acestea din urmă, dacă el a avut ceva confidenţial de spus, el a scris cifrat, schimbând ordinea alfabetului.” [11] Această metodă de criptare este cunoscută ca ,,Cifrul lui Cezar”, cu toate că metoda mai fusese folosită anterior.

Din documentul menţionat, reiese că în documentele secrete, Cesar folosea alfabetul latin, permutat ciclic cu 3 (D în loc de A şi aşa mai departe):

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 D E F G H I J K L M N O P Q R S T U V W X Y Z A B C

De exemplu: ,,MATEMATICA DE IERI SI DE AZI” devine după criptare: ,,PDWHPDWLFD GH LHUL VL GH DCL”

Despre criptografie Criptografia poate fi definită ca ştiinţa care studiază procedeele prin care conţinutul

mesajelor schimbate între membrii unui sistem poate fi făcut neinteligibil pentru exterioriul sistemului (criptarea si decriptarea) şi studiul condiţiilor metodelor efective sau potenţiale prin care din afara sistemului se poate realiza decriptarea (criptanaliza). [4]

Următoarea schemă prezintă un model general de care se ocupă criptografia:

Text clar Text criptat Text clar

Cheie k Cheie k’

Expeditorul (personalizat în

destinatarului (numit Bob) un mesinterceptat de un criptanalist (Oscar) acesta nu îi este destinat. Confidenţiarescrierea mesajului sub o formă careintercepta.[2] Confidenţialitatea este u

În cele ce urmează vor fi definMesajul (text) : un şir finit de caracterMesajul clar : mesajul ce urmează a Mesajul criptat : mesajul obţinut în urCriptarea : procesul prin care se realiDecriptarea : procesul prin care se reSistem de criptare (criptosistem): pacriptare – decriptare.

Pentru realizarea întregului prBob să stabilească, într-o etapă prelimde dispozitive automate care să schimbate.

În studiul unui criptosistem, cprin care din cunoaşterea unei mulţimrespectiv cheile utillizate şi metodele

Criptanaliza stabileşte gradulvulnerabilitate ale sale. Criptosistemeun grad mediu de vulnerabilitate, suinformatice în societate.

De exemplu, un mesaj criptatcunoaşte cheia, prin: 1. Atac prin forţă brută - testând fiecade deplasări posibile) până la obţinere2. Analiza frecvenţei caracterelor îcaracterelor din textul criptat cu cele

CRIPTANALIST

majoritatea lucrărilaj printr-un canal dcare doreşte din diverslitatea solicitată de Ali să nu poată fi înţeleasn obiectiv important î

iţi (conform [4]) termee dintr-o listă dată numfi prelucrat pentru obţima prelucrării mesajuzează obţinerea mesajualizează obţinerea meschetul de algoritmi pr

oces de transmitere a iinară, modalităţile de

realizeze personaliza

riptanaliza sistemului de mesaje criptate s

de criptare - decriptare de siguranţă al unuile a căror criptanaliză nt etichetate ca nesig

prin criptosistemul C

re variantă de deplasara unui text cu înţeles;

n text. [9] Prin comp ale literelor din alfa

DESTINATAR (DECRIPTARE)

EXPEDITOR (CRIPTARE)

or cu apelativul Alice) trimite e comunicaţie. Mesajul poate fi e motive să cunoască mesajul, deşi ce şi Bob se rezolvă de obicei prin ă de nici o persoană care l-ar putea n securitatea informaţiei. nii utilizaţi: ită alfabet.

nerea mesajului criptat. lui clar. lui criptat din mesajul clar.

ajului clar din mesajul criptat. in care se realizează operaţiile de

nformaţiei este necesar ca Alice şi criptare-decriptare sau să dispună t criptarea-decriptarea mesajelor

i înseamnă investigarea metodelor e pot afla mesajele clare aferente - corespunzătoare. [4] criptosistem, respectiv grade de demonstrează că acestea posedă un ure, deci puţin utile în aplicaţiile

ezar poate fi decriptat uşor, fară a

e (în cazul alfabetului latin sunt 26 ararea frecvenţelor de apariţie a

betul limbii curente se pot realiza

corespondenţe caracter-litere urmate de stabilirea cheii de criptare. Astfel, pentru sistemul Cezar este suficientă determinarea unei singure perechi caracter-literă.

Sisteme de criptare Un sistem de criptare (criptosistem)[2] este o structură Q = (P, C, K, E, e, D, d), unde:

P = {w | w � V *} este mulţimea ”textelor clare”, peste un alfabet nevid V, C = {w | w � W*} este mulţimea ”textelor criptate”, peste un alfabet nevid W (uzual W=V), K este o mulţime de elemente numite chei. E este o mulţime de funcţii injective P→C, numite funcţii de criptare, D este o mulţime de funcţii C→P numite funcţii de decriptare. Funcţiile e(k): P→C şi d(k): C→P vor fi notate cu ek, respectiv dk, şi se vor numi funcţia/metoda de criptare în cheia k, respectiv funcţia/metoda de decriptare în cheia k. Datele de mai sus trebuie să îndeplinească condiţiile:

(�k)(k � K) şi (�w)(w � P), dk(ek(w)) = w, (�)w � P

Funcţiile ek sunt injective; dacă fiecare ek este şi bijectivă (deci dk = ek -1),

criptosistemul se numeşte ”simetric”. De exemplu, în cazul sistemului de criptare Cezar, putem considera că V conţine

literele alfabetului latin cărora le putem asocia în ordine numerele întregi din intervalul [0, 25]:

Tabelul 1 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

0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25

Prin această asociere criptarea şi decriptarea pot fi operate in inelul finit Z26. Criptarea se face utilizând : ek(xi) = k + xi mod26= yi

Text clar M A T E M A T I C A

Numere asociate (xi) 12 0 19 4 12 0 19 8 2 0 Cheie k = 13 13 13 13 13 13 13 13 13 13 13

xi+ k 25 13 32 17 25 13 32 21 15 13 Suma mod. 26= yi 25 13 6 17 25 13 6 21 15 13

Text criptat Z N G R Z N G V P N

Decriptarea se face utilizând funcţia inversă: dk(yi) = yi – k mod26 = xi Se observă că în exemplul dat a fost folosită cheia k = 13 pentru fiecare caracter din

textul clar. Un sistem de criptare având un grad înalt de siguranţă este sistemul fluid de criptare.

Spre deosebire de sistemul de criptare Cezar, acesta, asociază fiecărui caracter din textul clar un număr dintr-un şir de numere care formează cheia fluidă.

O cheie fluidă a criptosistemului Q, este orice secvenţă (infinită) k=k1k2k3... de elemente din K. [2], [5] Pentru fiecare text clar w = x1...xj...xn, criptarea şi decriptarea se fac dupa relaţiile (1) şi (2)

ek(x1...xj...xn) = ��� (x1) ...��� (xj) ...��� (xn) = y1 ...yj ...yn (1) dk(y1 ...y j ...yn) = ��� (x1) ...��� (xj) ...��� (xn) = x1 ...xj ...xn (2)

Problema principală în realizarea unor sisteme de criptare fluidă Q (stream ciphers) sigure o reprezintă metoda (algoritmul) prin care se generează cheia fluidă. Un astfel de algoritm se numeşte generator de chei fluide (stream key generator -SKG) [2], [5].

Există două tipuri de bază de generatoare utilizate pentru producerea de secvenţe aleatoare: generatoare de numere aleatoare (RNGS) şi generatoare de numere pseudoaleatoare (PRNGS).

Ca RNGS pot fi utilizate surse non-deterministe cum ar fi surse fizice care generează evenimente întâmplătoare (zgomotul dispozitivelor semiconductoare, white noise), timingul unor procese (mişcările mouse-ului) etc. Problema utilizării unor astfel de surse în criptografie este dată de faptul că secvenţele obţinute nu sunt perfect aleatoare, ele necesitând prelucrări ulterioare; sursele nu pot fi disponibile simultan atât expeditorului cât şi destinatarului mesajului. Din aceste motive sunt preferate PRNGS.

PRNGS au la bază algoritmi care pleacă de la o secvenţă mică (seed) pe baza căreia se generează o infinitate de blocuri de numere. Pot fi introduse transformări care să elimine statistic corelaţiile dintre intrare şi ieşire. Numerele obţinute se numesc numere pseudoaleatoare.

O caracteristică importantă a numerelor aleatoare şi pseudoaleatoare utilizate în criptografie ar trebui să fie impredictibilitatea. [1]

Shannon şi teorema secretului perfect Claude Elwood Shannon (1916 – 2001) a avut contribuţii deosebite în teoria

comunicaţiilor. Un rezultat important privind obţinerea secretului perfect în criptografie este exprimat prin următoarea teoremă:

Teorema secretului perfect a lui Shannon [2], [7] afirmă că dacă P, C, K sunt mulţimi finite cu acelaşi cardinal (=�=�) şi dacă toate valorile p1(w), P∈w , sunt pozitive (i.e. >0) atunci Q, p1, p2 garantează secretul perfect dacă şi numai dacă următoarele două condiţii sunt satisfăcute:

(3) (� ) (w�P), (��) ) (c�C), (�� �) (k�K) aî ek(w) = c (4) fiecare cheie este utilizată cu o probabailitate egală cu �

� (cheile din K sunt uniform distribuite);

De observat importanţa utilizării unei chei fluide in care distribuţia caracterelor cheii să fie echiprobabilă.

De exemplu pentru un alfabet finit V = {a, b} şi K = {k1, k2}, pentru o frecvenţă dată de apariţie a literelor a şi b în textul clar, de exemplu pa = 1/3 şi pb = 2/3, dacă cheile ki � K au o probabilitate de apariţie egala, adică de 1/2 pentru cazul considerat, distribuţia caracterelor din textul criptat este echiprobabilă.

K/V a b k1 0 1 k2 1 0

În textul cifrat C:

pc(0) = �� � �� + �� � �� = ��

pc(1) = �� � �� + �� � �� = ���

Se observă că în cazul unei distribuţii echiprobabile pentru caracterele cheii, se obţine o distribuţie echiprobabilă a caracterelor textului criptat şi deci un nivel înalt de siguranţă a criptării (nu mai pot fi utilizate metodele statistice de criptanaliză).

Din condiţiile (3) şi (4) rezultă că problema esenţială în realizarea unor sisteme fluide de criptare sigure o reprezintă obţinerea sau generarea unor chei de criptare fluidă care să satisfacă anumite condiţii [6], cum ar fi: (c1) lungimea cheii fluide (teoretic infinită) trebuie să acopere întreg mesajul ce urmează să fie criptat; (c2) cheia fluidă trebuie să prezinte o structură formată din secvenţe de caractere aleatoare, caz în care sunt realizate confuzia şi difuzia caracterelor textului criptat; (c3) utilizarea unei chei fluide doar pentru o singură criptare, fără a o mai utiliza ulterior şi schimbarea ei la criptarea unui text nou (este o condiţie a secretului perfect).

Sistemele fluide de criptare prezintă unele inconveniente: (d1) dificultatea realizării unei chei fluide aleatoare; astfel există surse fizice care generează evenimente întâmplătoare (zgomotul dispozitivelor semiconductoare, white noise etc) dar aceste evenimente aleatoare fizice nu sunt disponibile atât expeditorului cât şi destinatarului mesajului; din aceast motiv în criptare sunt utilizate cheile fluide obţinute prin generatoare de numere pseudoaleatoare; (d2) cheia fluidă trebuie cunoscută atât de expeditorul cât şi de destinatarul mesajului, fapt ce implică comunicarea în mod confidenţial a unei chei de mărime egală cu mărimea textului clar; dacă ar exista această posibilitate, criptarea nu ar mai fi necesară; (d3) dezavantajul anterior este evitat prin utilizarea unor chei fluide generate prin algoritmi cunoscuti atât de destinatarul cât şi de receptorul mesajului; prin urmare în acest caz nu mai este necesară transmiterea cheii dar, dezavantajul procedeului e dat de faptul că algoritmii utilizaţi generează numere pseudoaleatoare.

Chei fluide prin numere iraţionale Ideea utilizării numerelor iraţionale intr-o problemă legata de criptografie a apărut în

urma comentariilor făcute la un curs [4], privind posibilitatea ca printr-un şir finit de caractere şi intr-un interval finit de timp să se transmită o cantitate infinită de informaţii, respectiv dacă este posibilă codificarea printr-un număr finit de caractere a unei cantităţi infinite de informaţii. Această posibilitate este argumentată în continuare.

Mulţimea numerelor iraţionale este infinită. În general, un număr iraţional poate fi codificat printr-un singur simbol (sau printr-un şir finit de caractere prin care se denumeşte), de exemplu, � (pi) sau �� (radical din şapte), el însă conţinând un număr infinit de zecimale (în orice bază). Această caracteristică elimină dezavantajul (d2) referitor la transmiterea confidenţială a unei chei de mărime egală cu mărimea textului clar deoarece nu trebuie transmis decât simbolul sau o descriere codificată a numărului iraţional din care se obţine cheia fluidă.

Un număr iraţional poate fi scris sub formă de număr zecimal. Şirul de zecimale al unui numar iraţional dat este infinit. Astfel pot fi îndeplinite condiţiile (c1) şi (c3). Zecimalele numărului iraţional se pot determina pe baza unor algoritmi sau utiliznd liste cu valorile numerice pentru un anumit număr de zecimale. Deşi nu este posibilă indicarea scrisă a înşiruirii infinite a zecimalelor în ordinea lor de apariţie, sunt disponibili algoritmi (dezvoltări în serie, sumarea seriilor convergente şi aproximări) şi medii de programare (Mathematica) sau site-uri specializate, prin care se poate afla zecimala a n-a pentru fiecare n dat. O listă a primelor 106 zecimale a unor numere iraţionale, este disponibilă în referinţa [10].

În 1909 Emile Borel a introdus conceptul de numere normale, demonstrând că aproape toate numerele reale sunt normale în sensul în care mulţimea numerelor non-normale are măsura Lebesque egală cu zero. Următoarele teoreme ilustrează acest concept. Teorema (1): aproape toate numerele conţin în partea lor zecimală (baza 10) orice cifră posibilă, şi conţin de asemenea, orice secvenţă finită de cifre dată. [3, p. 154, theorem 143]; Teorema (2): aproape toate numerele, atunci când sunt scrise în orice bază R, conţin în secvenţa de R-zecimale orice R-cifră posibilă şi orice secvenţă finită de R-cifre [3, p. 154, theorem 143]; Teorema (3): aproape toate numerele, atunci când sunt scrise în orice bază R, au proprietatea

că fiecare R-cifră are frecvenţa R1

în dezvoltarea lor R-zecimală şi orice secvenţă finită de R-

cifre mrrr L21 (indiferent de mărimea lui m) are frecventa mR

1 în dezvoltarea lor R-zecimală

[3, p.160, theorem 148]. Numerele care respectă Teorema (3), se numesc numere normale. [3] Toate numerele

normale sunt iraţionale; un număr raţional periodic nu posedă proprietatea (3). În particular, aproape toate numerele iraţionale au, în dezvoltarea zecimală (în baza 10), fiecare cifră cu o frecvenţă de apariţie de 1/10 şi, de asemenea, au în dezvoltarea zecimală (în baza 10) fiecare grup de două cifre, 21kk cu o frecvenţă de apariţie de 1/100, şi fiecare grup de trei cifre,

321 kkk apare cu o frecvenţă de 1/1000; în plus, aceste rezultate sunt adevărate pentru orice altă bază R şi prin urmare şi pentru baza 26 care este utilizată pentru criptarea textelor clare.

Prin urmare: dacă vom alege pentru obţinerea unei chei fluide, un număr iraţional β care aparţine clasei numerelor normale, atunci în şirul zecimalelor numărului β fiecare m-tuplu (i.e., fiecare element al lui K) apare cu frecvenţa �

���. uniform distribuite. În consecinţă este îndeplinită şi condiţia aleatorismului (c2) şi sunt eliminate dezavantajele (d1) şi (d3).

În concluzie, am arătat că numerele iraţionale pot îndeplini condiţiile (3) şi (4) ale Teoremei secretului perfect a lui Shannon.

Exemple de aplicare pe text În cele ce urmează, numerele iraţionale vor fi scrise în baza 10. Textele clare ce

urmează a fi criptate printr-o cheie fluidă vor fi scrise în alfabetul englez (latin) format din 26 de litere. Acestora li se vor asocia numerele întregi din intervalul [0, 25], ca în criptosistemul Caesar. În acest mod se va putea opera matematic în inelul Z26.

Realizarea cheii fluide dintr-un număr iraţional presupune următorii paşi: (1) alegerea unui număr iraţional β = B,b1 b2 b3 ... bN ..., ale carui prime N zecimale (scrise în baza 10) pot fi obţinute uşor pe baza unui algoritm sau dintr-o listă cu N suficient de mare [10]; (2) selectarea unui rang i; acesta va reprezenta valoarea parametrului n0; valoarea lui i indică locul primei zecimale, din şirul de zecimale ale numărului iraţional, de la care se consideră secvenţa de zecimale utilizată la obţinerea cheii fluide; de exemplu pentru valoarea i, secvenţa de zecimale extrase din şirul de zecimale ale numărului iraţional va fi q = bi bi+1 bi+2…; (3) prelucrarea secvenţei q prin algoritmi care să producă substituţia, deplasarea şi difuzia caracterelor. Acest pas este util pentru a elimina posibilitatea de a determina numărul iraţional utilizat în cazul criptanalizei cu text clar; rezultă o nouă secvenţă k utilizată drept cheie fluidă.

Vor fi prezentate două metode de criptare a unui text clar prin intermediul unei chei fluide obţinută dintr-un număt iraţional, urmând paşii (1) – (3). [6] În prima metodă, cheia fluidă este chiar secvenţa q, dependentă de valoarea i a parametrului n0. În metoda a doua, cheia fluidă se va obţine din secvenţa q, grupând câte două zecimale consecutive şi considerând fiecare pereche un număr întreg mai mic decât 100; după reducerea mod26 a acestor numere obţinem o nouă secvenţă pe care o vom folosi drept cheie fluidă. Având în vedere ca gruparea se poate face, în general, pentru n1 zecimale consecutive, cheia fluidă va fi în acest caz o secvenţă de resturi mod26 de numere naturale mai mici decât 10�1. Prin urmare, n1 este un parametru pentru metoda a doua.

Metodele vor fi exemplificate pentru pentru textul clar: CRIPTANALIZA (12 litere) scris în alfabetul "latin" (26 de litere). Literele vor fi codate cu numere întregi din inelul Z26:

P = C = K = Z26

Metoda 1 Pasul (1): Se alege un număr iraţional, de exemplu: ��=2,64575131106459059050161575363926042571025918308245018036833445920

106... Pasul (2): alegem i=1 (n0=1). Se vor folosi primele 12 zecimale, deci:

q =645751311064 = k.

Se criptează textul clar folosind pentru fiecare literă zecimala corespondentă a numărului iraţional ��. Se aplică:

���(xj)= bj+xj mod26

Criptarea este dată de rezultatul adunării în inelul Z26 a cifrelor care codează literele textului clar şi a zecimalelor corespunzătoare din cheia fluidă k (Tabelul 2).

Tabelul 2

Text clar C R I P T A N A L I Z A Numere asociate xj 2 17 8 15 19 0 13 0 11 8 25 0

bj 6 4 5 7 5 1 3 1 1 0 6 4 xj +bj 8 21 13 22 24 1 16 1 12 8 31 4

Suma mod. 26= yi 8 21 13 22 24 1 16 1 12 8 5 4 Text criptat I V N W Y B Q B M I F E

CRIPTANALIZA → IVNWYBQBMIFE

Decriptarea se face aplicând funcţia inversă textului criptat IVNWYBQBMIFE

(Tabelul 3):

���(yj) = yj - bj mod26

Tabelul 3 Text criptat I V N W Y B Q B M I F E

yi 8 21 13 22 24 1 16 1 12 8 5 4 bj 6 4 5 7 5 1 3 1 1 0 6 4

yi - bj 2 17 8 15 19 0 13 0 11 8 -1 0 Dif. mod26= xj 2 17 8 15 19 0 13 O 11 8 25 0

Text clar C R I P T A N A L I Z A

IVNWYBQBMIFE → CRIPTANALIZA

Metoda 2. Pasul (1): Se alege un număr iraţional, de exemplu: ��=2,64575131106459059050161575363926042571025918308245018036833445920

106... Pasul (2): alegând parametrul n0=i, atunci, secvenţa de zecimale utilizată la obţinerea

cheii fluide va începe cu a i-a zecimală a numărului iraţional (zecimala de pe poziţia i). Pasul (3): din secvenţa extrasă din şirul de zecimale al numărului iraţional ales se

formează un nou şir de numere prin gruparea a câte două zecimale consecutive (n1=2):

���� ���! …�"�"#� …���$���� ,

unde �"�"#� este %&'()*��+&��,')��+-*�.������/�)��0� 1 2�&'()*��+&3* 4 ,��+-*). �/�)��0 5 2� 6

Dacă textul clar este x = x1 x2 x3…xj… xn, atunci criptarea şi decriptarea se fac după

relaţiile (3) respectiv (4): ek(xj) = ��7$���7 +xj (mod 26) (5)

dk(cj) = cj - ��7$���7 (mod 26) (6)

Utilizând �� şi considerând n0=1 , n1=2 (= numărul de zecimale consecutive

considerate), obţinem secvenţa q = 64 57 51 31 10 64 59 05 90 50 16 15 = k. aceasta reprezintă cheia fluidă.

Se criptează textul clar folosind relaţia (5):

Tabelul 4 Text clar C R I P T A N A L I Z A

Numere asociate xj 2 17 8 15 19 0 13 0 11 8 25 0 bj 64 57 51 31 10 64 59 05 90 50 16 15

xj +bj 66 74 59 46 29 64 72 05 101 58 41 15 Suma mod. 26= yi 14 22 07 20 03 12 20 05 23 06 15 15

Text criptat O W H U D M U F X G P P

CRIPTANALIZA → OWEUDMUFXGPP

Decriptarea se face aplicând relaţia (6):

Tabelul 5 Text criptat O W H U D M U F X G P P

yi 14 22 07 20 03 12 20 05 23 06 15 15 bj 64 57 51 31 10 64 59 05 90 50 16 15

yi - bj -50 -35 -44 -11 -7 -52 -39 0 -67 -44 -1 0 Dif. mod26= xj 2 17 8 15 19 0 13 0 11 8 25 0

Text clar C R I P T A N A L I Z A

OWEUDMUFXGPP → CRIPTANALIZA

Remarcă. Nu ştim dacă �� este un număr iraţional cu o distribuţie normală a zecimalelor. În secţiunea următoare se vor prezenta unele date privind distribuţia zecimalelor acestui număr. Însă numărul iraţional:

β = 0.123456789 10 11 12… 100 101…

a cărui parte zecimală este obţinută prin scrierea în ordine crescătoare a numerelor întregi pozitive, este un număr iraţional cu distribuţie normală a zecimalelor. [3, p. 163]. Prin urmare, pentru numărul iraţional β, orice sistem fluid de criptare obţinut prin metoda 2, asigură conditia secretului perfect.

Distributia zecimalelor numarului irational�� Secţiunile precedente au subliniat importanţa structurii cheii fluide în obţinerea unui

criptosistem fluid, respectiv, importanţa distribuţiei cifrelor sau a grupurilor de cifre din şirul zecimalelor numărului iraţional. Toate exemplele anterioare au utilizat pentru obţinerea cheii fluide numărul iraţional ��. Liste complete privind zecimalele unor numere iraţionale pot fi găsite în referinţa [10].

Observaţie: Determinarea faptului că anumite numere sunt normale este o problemă nerezolvată. Încă nu se cunoaşte în mod fundamentat matematic dacă �, ln2, e, �8, sunt numere normale (Bailey, Crandall, 2003). Ele sunt presupuse a fi normale pe baza unor dovezi empirice. De exemplu, primele 30 de milioane de zecimale ale lui � sunt uniform distribuite (Bailey, 1988). [12]

În cele ce urmează se vor face unele precizări privind distribuţia zecimalelor numărului

iraţional ��. [6] Distributia zecimalelor numarului irational�� (Tabelul 6; Diagrama 1):

Tabelul 6

Zecimala

0

1

2

3

4

5

6

7

8

9

Total zecimale

Frecvenţa absolută

99767 99640 100506 100216 99801 100190 99826 100196 99943 99939 1000024

Diagrama 1

Analiza Scatter a distribuţiei zecimalelor numarului irational�� (Diagrama 2):

Diagrama 2

Distributia zecimalelor numarului irational�� luate câte două; s-au considerat 500012 grupe de câte două zecimale (Diagrama 3):

Diagrama 3

0 1 2 3 4 5 6 7 8 9

99767 99640 100506100216 99801 100190 99826 100196 99943 99939

Frecventa de aparitie a zecimalelor

99400

99600

99800

100000

100200

100400

100600

0 2 4 6 8 10

Frec

vent

a

Zecimale

Series1

Linear (Series1)

0

1000

2000

3000

4000

5000

6000

Analiza Scatter a distribuţiei zecimalelor numarului irational�� luate câte două; s-au considerat 500012 grupe de câte două zecimale (Diagrama 4):

Diagrama 4

Bibliografie

[1]Andrew Rukhin, Juan Soto, James Nechvatal, Miles, Smid, Elaine Barker, Stefan Leigh, Mark Levenson, Mark, Vangel, David Banks, Alan Heckert, James Dray, San Vo A Statistical Test Suite for Random and Pseudorandom Number Generators for Cryptographic Applications, National Institute of Standards and Technology-Technology Admionistration, U.S. Departament, p1-1 [2] Atanasiu, A., Securitatea informatiei [Information Protection, in Romanian] Vol.1, Ch.4, Ed. INFODATA, Cluj, 2008, p 6; 7; 10; 47 [3] Hardy, G.H. and Wright, E.M., An Introduction to the Theory of Numbers, 6th ed., Oxford Univ. Press, 2008, p148;153;154 [4] Ioniţă, C., Lecture notes on the mathematics used in cryptography [in Romanian, manuscript], TCSI, 2010 [5] Menezes,A., Oorschot,P., Vanstome,S., Handbook of Applied Cryptography, CRC Press, 1996 [6] Neagoe, M., C., Stream Keys by Irrational Numbers, Proceedings of the 4th International Conference of Security for Information Technology and Communications, Bucharest, 2011 [7] Rothe, J., Complexity Theory and Cryptology -An Introduction to Cryptocomplexity, Springer-Verlag, 2005 [8] Shannon, C. E. (1946), Communication Theory of Secrecy Systems (A Mathematical Theory of Cryptography), http://202.38.64.11/~whli/lecture-crypto-pb/materials/, p 681 [9] Simion, E., Statistical tools used in cryptographic evaluation; http://imar.ro/organization/activities/standalone/congmatro2011/talks.php [10] http://apod.nasa.gov/htmltest/gifcity/sqrt7.1mil [11] Ancient History Sourcebook: Suetonius, De Vita Caesarum, [http://www.fordham.edu/halsall/ancient/suetonius-julius.asp], [12] http://mathworld.wolfram.com/NormalNumber.html

4750480048504900495050005050510051505200

0 20 40 60 80 100 120

Frec

vent

a

Grupe zecimale

Series1

Linear (Series1)