Blum – un mic exemplu

Să ne reamintim ce sunt întregii Blum:

Un număr n este întreg Blum dacă şi numai dacă n este de forma pt1*qt2 , unde p ≡ q ≡ 3 (mod 4) iar t1 şi t2 sunt numere întregi impare.

Haideţi să simţim puţin acest tip de întregi alegându-ne noi două numere prime distincte, p şi q, de forma 4k+3.

p ≡ q ≡ 3 (mod 4)

Fie p=3 şi q=7, atunci n=21.

Câte elemente va avea mulţimea Zn*?  (Mulţimea numerelor din Zn co-prime cu n)

fi(n) = fi(p) * fi(q) = (p – 1) * (q – 1) = 12
|Z21*| = 12
Z21= {1, 2, 4, 5, 8, 10, 11, 13, 16, 17, 19, 20}

Dintre acestea unele sunt reziduuri pătratice şi, deci, au simbolul Jacobi egal cu 1 modulo n, altele sunt reziduuri non-pătratice atât modulo p cât şi modulo q, şi, deci, simbolul lor Jacobi modulo n va fi tot 1 deoarece (-1) * (-1) = 1, iar altele vor fi reziduuri pătratice modulo unul din cele 2 numere prime, p sau q dar reziduuri non-pătratice modulo celălalt număr prim, şi atunci simbolul lor Jacobi va fi (-1) * 1 = -1 sau 1 * (-1) = -1.

În ceea ce priveşte cardinalul acestor 3 mulţimi putem spune că jumătate din elementele mulţimii  Zn* vor avea simbolul Jacobi 1 şi jumătate -1. Iar din cele care au simbolul Jacobi 1, jumătate sunt reziduuri pătratice modulo n şi jumătate sunt non-reziduuri pătratice modulo n. Haideţi să vedem care:

QR21 = {1, 4, 16}
J21 – QR21 = QNR21 = {5, 17, 20}
Z21*J21 = {2, 8, 10, 11, 13, 19}

De ce acestea? Putem da uşor răspunsul dacă facem calculele modulo p şi modulo q:
(cele scrise cu roşu sunt reziduurile pătratice modulo p, respectiv q)

Z3* = {1, 2}
QR3 = {1, 4 (mod 3), 10  (mod 3), 13 (mod 3), 16 (mod 3), 19 (mod 3)}
J3QR3 = QNR = {2, 5 (mod 3),8 (mod 3), 11 (mod 3), 17 (mod 3), 20 (mod 3)}

Z7*  = {1, 2, 3, 4, 5, 6}
QR7 = {1, 2, 4, 8 (mod 7), 11 (mod 7),  16 (mod 7)}
J7QR7 = QNR7 = {5, 10 (mod 7), 13 (mod 7), 17 (mod 7), 19 (mod 7), 20 (mod 7)}

Iar acum să ne convingem prin metoda „muncitorească”:

12 ≡ 1 mod 21
22 ≡ 4 mod 21
42 ≡ 16 mod 21
52 ≡ 25 ≡ 4 mod 21
82 ≡ 64 ≡ 1 mod 21
102 ≡ 100 ≡ 16 mod 21
112 ≡ 121 ≡ 16 mod 21
132 ≡ 169 ≡ 1 mod 21
162 ≡ 256 ≡ 4 mod 21
172 ≡ 289 ≡ 16 mod 21
192 ≡ 361 ≡ 4 mod 21
202 ≡ 400 ≡ 1 mod 21

După cum putem observa, singurii întregi reziduuri pătratice modulo 21 sunt 1, 4 şi 16. Să observăm acum ce putem spune despre -1, -4 şi -16:
-1 ≡ 20 mod 21
-4 ≡ 17 mod 21
– 16 ≡  5 mod 21
Putem uşor observa că 5, 17 şi 20 nu sunt reziduuri pătratice dar, ceea ce e important, au simbolul Jacobi 1. Aşadar, dacă vom avea de-a face cu numere mari, pentru care nu este fezabil să se calculeze factorizarea lor, atunci va fi o problemă dificilă ca, fără a cunoaşte p şi q, să se poată spune dacă un număr din Zn* este sau nu reziduu pătratic.

Reclame

Întregii Blum şi simbolul Jacobi

blum1   După cum menţionează Encyclopedia of Cryptography and Security, un întreg Blum, (denumit după Manuel Blum, cel care a evidenţiat utilitatea acestor întregi în criptografie)  este un înteg pozitiv n, produs a două numere prime p şi q, ambele congruente cu 3 modulo 4.

pq ≡ 3 (mod 4)

Când facem calcule modulo un întreg Blum,

x← (mod n)

se numeşte o permutare cu trapă sau funcţiue one-way cu trapă. Şi să vedem despre ce este vorba. Pentru un reziduu pătratic modulo n, cu n întreg Blum, vom avea 4 rădăcini pătratice (mod n). Dintre acestea una singură va fi şi ea, la rândul său un reziduu pătratic. Trapa constă în faptul că poţi ajunge uşor (printr-un algoritm de complexitate timp polinomială) la această rădăcină dacă deţinem factorizarea lui n, adică să cunoaştem numerele prime p şi q. Mai concret care ar fi paşii de a ajunge la această rădăcină?  Mai întâi vom obţine toate cele 4 rădăcini pătratice (două modulo p şi două modulo q) astfel vom rezolva ecuaţia:

 ≡ a (mod p),

 obţinând soluţia prin:

x ≡ ±a^((p+1)/4) (mod p), deoarece  p ≡ 3 (mod 3).

O dată găsite cele 4 rădăcini pătratice urmează identificarea aceleia dintre ele care este reziduu pătratic modulo n. Cum facem aceasta? Calculând simbolul Legendre al acestor rădăcini modulo p respectiv q. După cum ştim, simbolul Legendre ne ajută să aflăm dacă un întreg este reziduu pătratic sau nu modulo un număr prim.

Ca o mică paranteză, generalizarea simbolului Legendre este simboul Jacobi care nu mai este restrâns doar la modulii care sunt numere prime, diferenţa majoră fiind că primul simbol ne certifică dacă un întreg este reziduu pătratic sau nu, în timp ce simbolul Jacobi ne poate preciza cu siguranţă doar dacă întregul nostru nu este reziduu pătratic; altfel ne spune că „poate fi” (sau nu) reziduu pătratic modulo un număr compus.

Astfel, un întreg a se numeşte reziduu pătratic modulo n dacă există un întreg pozitiv astfel încât  ≡ a (mod n). Simbolul Jacobi este al lui a modulo n (sJ) este egal cu 0 dacă a divide n, -1 dacă a nu este reziduu pătratic iar dacă a este reziduu pătratic, atunci simbolul Jacobi (sJ) va fi egal cu 1. Dar dacă sJ a(mod n) = 1 acest lucru nu implică faptul că a este reziduu pătratic modulo n. Vom continua seria de articole prezentând o schemă de criptare cu chei publice ce foloseşte astfel de întregi Blum.

(va urma 🙂 )    

Criptarea Bazata pe Identitate

Acest concept interesant a aparut datorita lui Adi Shamir care l-a initiat in anul 1984. El a venit si cu o schema de semnatura digitala.

De atunci a fost nevoie de mai multi ani pana la concretizarea acestui tip de criptare, o subcategorie a criptarii cu chei publice dar care, spre deosebire de creiptarea generala cu chei publice (PKE), utilizeaza ca cheie publica ID identitatea destinatarului sau orice sir de caractere (string) derivat din ID.

Avantajul principal ar fi acela ca este eliminat procesul greoi de manageruire a cheilor publice, lantul nesfarsit de certificate necesare pentru a-mi garanta faptul ca acea cheie publica pe care o folosesc este intr-adevar a destinatarului caruia eu doresc sa ii transmit mesajul.

In cadrul IBE nici nu mai este nevoie sa ma asigur ca destinatarul are generata o cheie publica deoarece voi folosi, de exemplu, numarul sau de telefon sau adresa sa de email, care il defineste in mod unic si este cunoscuta public.

Orice schema care se bazeaza pe acest concept are ca structura 4 algoritmi probabilisti, polinomiali ca timp ( prescurtat  PPT). In cadrul primului algoritm, Setup, ce primeste la intrare doar parametrul lambda (parametrul de securitate ce reprezinta pe cati biti lucram), se stabilesc parametrii publici PP ai schemei impreuna cu cheia master, msk. La acest pas se va utiliza o functie hash din multuimea acestor functii pentru a obtine cheia publica corespunzatoare ID.

Al doilea algoritm KeyGen genereaza cheia privata corespunzatoare identitatii ID respective, in vreme ce ultimii doi algoritmi fac criptarea, Encrypt, respectiv decriptarea Decrypt. La criptare parametrii de intrare sunt mesajul m impreuna cu parametrii publici si cheia publica, iar decriptarea necesita la intrare criptotextul impreuna cu cheia privata, pentru a ajnge din nou la mesajul initial.

 

Şcoala de vară, 12-15 iulie 2016, Sinaia

În cadrul proiectului Horizon 2020 se va organiza la Sinaia o şcoală de vară, EBSIS Summer School on Distributed Event Based Systems and Related Topics 2016,  între 12-15 iulie a.c. ce va avea ca tematică sisteme distribuite şi securitate. Evenimentul va fi organizat de Univ. „Al. I. Cuza” Iaşi, Univ. Neuchatel, Elveţia şi Univ. Tehnică din Desden, Germania.

Câteva dintre tematicile ce vor fi atinse pot fi găsite aici, legate de securitate, scalabilitate şi sisteme distribuite.

Studenţii doctoranzi sunt invitaţi să prezinte tematica tezei la care lucrează în cadrul unor sesiuni dedicate.

Împrejurimile sunt deosebit de frumoase, fiind situată în Carpaţii Meridionali. Costurile pentru cazare şi masă, pentru un număr limitat de participanţi afiliaţi uneia din universităţile ce organizează evenimentul va fi suportat în întregime de proiectul EBSIS (cazarea se va face în acest caz în aceeaşi locaţie în care se va ţine această şcoală de vară).

Vă aşteptăm cu drag să participaţi alături de noi!

Criptanaliza sistemului de criptare Vigenère

Blaise de Vigenere În cadrul criptosistemului Vigenère am putea face maparea între literele alfabetului şi numerele de la 0 la 25. Cuvintele peste această mulţime le vom putea forma folosi aceste numere. Vom avea nevoie şi de o cheie de criptare de lungime l minimum 1, peste mulţimea aceeaşi mulţime.

Criptând un text în clar m cu cheia k, vom obţine un text criptat pe care îl vom nota cu c.

Algoritmul de obţinere a criptotextului c presupune criptarea literă cu literă a textului iniţial astfel: se ia litera din textul clar (adică numărul corespunzător literei) de pe poziţia i şi se adună cu litera din cheie de pe poziţia (i-1) mod (l+1) iar după adunare se reduce totul modulo 26, câte litere avem în alfabet. Şi se aplică acest algoritm cu fiecare literă din mesajul iniţial, de la 1 la l.

Dacă citim caracterele din textul criptat din n în n, vom obţine un şir care va avea proprietăţile unui criptotext obţinut prin metoda substituţiei având ca pas de shiftare litera din cheia k de pe poziţia de pe care am început extragerea literelor din criptotext.

De exemplu:

n = 6; k = 8; iar poziţia de început în acest exemplu este tot 6.

aksiwnrh|cztpwjql|curntivm|gjtustwg|elgozpza|qbdhriym|duekflfi|otozshft|cbrrswks|ztcrbbo

şirul obţinut este njitpilhwb.

Pornind de la această observaţie, pentru a face criptanaliza acestui criptosistem ne vom putea folosi de câteva tehnici aplicabile pe criptotext criptate prin substituţie monoalfabetică, cum ar fi frecvenţa literelor, a digramelor, a trigramelor dar acest pas îl putem face după ce cunoaştem lungimea cheii de criptare k. Pentru a depista această lungime vom putea folosi un alt parametru statistic, care de asemenea are o valoare diferită şi specifică de la o limbă la alta, iar acest parametru se numeşte indice de coincidenţă.

Ce reprezintă şi cum ne poate fi de folos?

Îl vom nota IC(m) şi cuantifică probabilitatea ca două caractere extrase la întâmplare dintr-un text să coincidă. Calculul se face pornind de la numărul de apariţii ale simbolului respectiv în textul (limba) în cauză.

Ceea ce este demn de remarcat este faptul că acest indice de coincidenţă nu se modifică în urma criptării prin substituţie. Astfel, procedeul de aflare a lungimii cheii se foloseşte de calcularea indicelui de coincidenţă pentru şiruri de caractere construite din criptotext ca mai sus. Se începe de la n = 1, se calculează IC(şir), se compară valoarea rezultată cu valoarea standard pentru limba în care este scris textul în clar. Dacă diferenţa este semnificativă, se continuă incrementarea lui n până când valoarea indicelui de coincidenţă pentru şirul obţinut este foarte apropiată de valoarea standard a limbii respective.

După ce am aflat lungimea cheii urmează procesul de decriptare utilizând frecvenţa literelor. Vom folosi acelaşi procedeu de creare a şirurilor pe care le putem considera acum ca fiind criptate prin substituţie monoalfabetică şi, ca urmare, vom afla literele din cheie rând pe rând folosind statisticile limbii în care a fost scris mesajul original.

Mult succes la criptanaliză!

P.S. Vă voi da un text criptat cu criptosistemul Viegenère pentru a creşte interesul studierii acestui subiect. J