înregistrare Logare
Puncte:0
Tom avatar Crypto

Algoritm de criptare simetric bazat pe multiplicare

drapel tf
Tom

De ceva vreme ma intreb despre acest paragraf:

Înmulțirea este o funcție excelentă de amestecare. Dacă descoperi cum arată multiplicarea în termeni de AND și XOR, devine evident cât de elaborată este o înmulțire pe 64 de biți. Cantitatea de tranzistori necesare pentru implementarea acestuia în hardware interzice utilizarea multiplicarii în majoritatea algoritmilor criptografici. Dar pentru PRNG-urile non-criptografice care trebuie să ruleze doar pe un CPU de uz general, multiplicarea este foarte utilă deoarece există deja o implementare hardware.

https://tom-kaitchuck.medium.com/designing-a-new-prng-1c4ffd27124d

De obicei, în algoritmii de criptare folosim operațiuni modulare de adăugare, rotație și SAU exclusive. Dar există ceva care ar putea sta în calea utilizării înmulțirii modulare, rotației și operațiunilor SAU exclusive?

Multiplicarea modulară este mai lentă decât adăugarea, dar probabil că nu este cu mult mai lentă și, cu siguranță, este o funcție de amestecare mai puternică. Înmulțirea este de fapt o funcție excelentă de amestecare, așa că de ce este atât de rar folosită în criptografia simetrică? Cred că chiar și smartphone-urile pot face înmulțirea pe 64 de biți foarte repede și au implementare hardware pentru multiplicare (dar nu sunt sigur).

Este într-adevăr încetineala înmulțirii o problemă atât de mare încât multiplicarea nu poate găsi o utilizare larg răspândită în algoritmii de criptare rapid și ușori? Probabil că pe dispozitive IOT sau cipuri RFID poate fi o problemă, dar când vine vorba de computere și smartphone-uri, un algoritm de criptare bazat pe multiplicare nu ar putea fi o problemă, nu-i așa?

96
0 + 0
phantomcraft avatar
drapel pf
phantomcraft
Dacă procesorul nu are un multiplicator hardware întreg, nu ar trebui să fie o problemă. Problema începe atunci când se folosește într-un mediu foarte mic, cum ar fi smartcard-urile, când procesorul mic face doar operațiuni de bază ca cele pe care le-ați citat,
1
Răspunde
Puncte:5
poncho avatar Crypto
drapel my
poncho

Este într-adevăr încetineala înmulțirii o problemă atât de mare încât multiplicarea nu poate găsi o utilizare larg răspândită în algoritmii de criptare rapid și ușori? Probabil că pe dispozitive IOT sau cipuri RFID poate fi o problemă, dar când vine vorba de computere și smartphone-uri, un algoritm de criptare bazat pe multiplicare nu ar putea fi o problemă, nu-i așa?

O parte a problemei pare să fie definiția termenului „ușor” și platformele vizate. Procesoarele de pe smartphone-uri sunt de fapt destul de capabile; Nu aș caracteriza acele platforme (sau computere laptop) ca fiind neapărat „ușoare”. Crypto-ul ușor este în general proiectat având în vedere microcontrolere; de obicei, acele microcontrolere nu au încorporate instrucțiuni de multiplicare pe 64x64 de biți.

Acum, multiplicarea modulară (pentru modul o putere de 2) poate fi implementată printr-o serie de deplasări și adunări condiționate; cu siguranță fezabil, dar considerabil mai scump decât o operațiune de adăugare.

Cealaltă problemă pare să fie că multiplicarea modulară nu este atât de minunată pe cât ai fi sperat. Pentru această discuție, îmi voi limita discuția la înmulțirea modulo o putere de 2 (multiplu modulo a prim nu are aceste probleme; au probleme în jurul intervalului care nu este o putere de 2).

  • Multiplicarea modulară nu are nicio propagare „cuvântul potrivit”; de exemplu, inversarea bitului înalt al uneia dintre intrări ar afecta doar bitul înalt al ieșirii; ceilalți biți nu sunt afectați. Desigur, adăugarea modulară are aceeași problemă; totusi este si mai ieftin.

  • Înmulțirea modulară are diferențe puternice; cel mai puternic se bazează în jurul identității $(-x)*y = -(x*y)$ (și modulul de operare nu descompune acest lucru).

Ambele probleme pot fi proiectate într-un design adecvat; cu toate acestea, faptul că trebuie să faceți acest lucru îl face mai puțin atractiv. În plus, se pune întrebarea: de ce să nu folosiți înmulțirea în $GF(2^k)$ in schimb? Dacă facem o implementare shift/add, o implementare dublă/xor a înmulțirii Galois nu este mult mai costisitoare și evită cele două probleme de mai sus...

0 + 0
Tom avatar
drapel tf
Tom
Desigur, modul de multiplicare 2^n are probleme mari cu amestecarea biților (mai ales scăzut), de aceea l-am combinat cu xor și rotație. Dar din câte știu, plusul are probleme și mai mari de acest tip. Nu sunt sigur, dar probabil diferențe chiar mai puternice.
0
Răspunde
Tom avatar
drapel tf
Tom
Înmulțirea GF(2^k) poate fi la fel de rapidă ca și multiplicarea numerelor pe 64 de biți mod 2^64? Cred că trebuie să fie GF(2^64) pentru a obține aceeași cantitate de biți.
0
Răspunde
poncho avatar
drapel my
poncho
@Tom: evident, orice astfel de răspuns ar fi destul de dependent de hardware. Pe procesoarele mari, cred că au operațiuni de „înmulțire fără transport”; reparația necesară nu este gratuită, așa că va fi mai lentă decât o multiplicare directă 64x64, dar nu ar fi rău. Pe procesoarele mici (fără o multiplicare), un xor dublu/condițional în timp constant $GF(2^{64})$ ar trebui să fie aproape de multiplicarea shift/condițională 64x64...
0
Răspunde
Tom avatar
drapel tf
Tom
Am făcut un generator LCG pe 32 de biți și un generator LCG în GF(2^32). Și înmulțirea în GF(2^32) perfmorms ușor mai rău în PractRand. Se pare că există și unele probleme cu biții mici. Nu vor mai fi alte diferențe? Nu sunt sigur. Se pare că înmulțirea în GF(2) nu amestecă mai bine biții. Sau poate că principalul avantaj este că este mai greu de găsit inversul multiplicativ?
0
Răspunde
poncho avatar
drapel my
poncho
@Tom: avantajul înmulțirii GF este următorul: dacă $a \ne 0$ și $b$ sunt necunoscute și distribuite uniform, atunci $a \times b$ va fi de asemenea distribuit uniform. Acest lucru nu este valabil pentru înmulțirea modulo o putere de 2, dacă $a = 2$ și $a \times b$ va fi întotdeauna par.
1
Răspunde
Puncte:4
avatar Crypto
drapel ye
garfunkel

Cifrul bloc IDEE din 1991 folosit multiplicare modulară mod $2^{16}+1$ pentru difuzie (unde 0 este mapat la $2^{16}$).

Deoarece divizorii zero nu sunt buni din punct de vedere criptologic, modulul ar trebui să fie prim și de forma $2^b+1$ cum se preferă să lucreze cu biți (și să nu folosească 0), deci $b=2, 4, 8, 16$ ($b=1$ ar fi liniară).

Dacă proiectați un cifr folosind aceste înmulțiri modulare, veți întâlni (cel puțin) două probleme:

  • proprietățile criptografice ale înmulțirilor modulare nu sunt bine înțelese, ceea ce face dificil pentru tine să arăți că cifrul tău este bun
  • pentru dispozitive mai mici, trebuie luate în considerare atacurile pe canale laterale, dar este greu să protejați aceste înmulțiri modulare împotriva acestora (mai ales împotriva DPA; dar atacurile de sincronizare ar putea fi deja o problemă, dacă multiplicarea nu este constantă în timp)
0 + 0
poncho avatar
drapel my
poncho
Aș susține că proprietățile criptografice ale înmulțirii modulare sunt înțelese. În plus, în ceea ce privește DPA, multiplicarea modulară este prietenoasă cu pragul, bazată pe identitatea $(A+B)*(C+D) = (A*C + B*D) + (A*D + B*C )$ (care se extinde în mod evident pentru pragurile cu 3+-căi)
0
Răspunde
Tom avatar
drapel tf
Tom
Atacurile pe canale laterale și atacurile de sincronizare sunt într-adevăr o problemă care trebuie luată în considerare, am uitat de asta. Totuși, adăugarea nu este la fel de vulnerabilă la asemenea probleme? Sau poate nu este pentru că îl putem transforma cu ușurință în shift și xors, care sunt timp constant?
0
Răspunde
poncho avatar
drapel my
poncho
@Tom: principala problemă cu sincronizarea și înmulțirea este pe platformele de vârf, pe acele platforme, instrucțiunea de multiplicare ar putea să nu fie constantă în timp (de exemplu, opriți-vă când unul dintre operanzi epuizează biții „1”). Acum, puteți implementa o multiplicare în timp constant pe acele platforme; cu toate acestea, un implementator cripto-naïv s-ar putea să nu. În schimb, CPU-urile implementează aproape întotdeauna adăugarea în timp constant...
1
Răspunde
Tom avatar
drapel tf
Tom
Inca o intrebare. Pentru a obține analog de înmulțire pe 64 de biți (mod 2^64), ce GF ar trebui folosit? Vreau să înmulțesc numere pe 64 de biți și să obțin rezultate pe 64 de biți. Am dreptate că trebuie să folosesc GF(2^64)? Există exemple de GF(2^8) peste tot, AES operează și pe GF(2^8), dar funcționează pe octeți.Dacă cineva ar dori să înlocuiască înmulțirea pe 64 de biți, trebuie să folosească GF(2^64), am dreptate? Sau poate că ar putea fi ceva diferit, ca în AES GF(2^8), dar pe octeți? Atunci regulile unei astfel de aritmetici sunt ușor diferite, decât în ​​GF(2^64), dacă am înțeles bine.
0
Răspunde
drapel ye
garfunkel
@poncho: Formulele pe care le-ați dat pentru implementările de prag ascund două probleme de implementare: Adăugarea este mod $2^{16}+1$, astfel încât părțile aditive nu se potrivesc în 16 biți și aveți nevoie de o reducere modulară care este ușor de implementat , dar trebuie să luați în considerare că valorile nereduse sunt vizibile pentru atacator (prin DPA). Dar adevăratele probleme pentru o implementare securizată DPA vor apărea, atunci când amestecați înmulțirea modulară cu alte operațiuni precum xor sau modul de adăugare $2^{16}$, deoarece trebuie să comutați între diferite operații de mascare, ceea ce nu este banal. (și consumatoare de timp).
0
Răspunde
drapel ye
garfunkel
@Tom: Știți că înmulțirea în câmpul cu elemente $2^{64}$ este destul de diferită de modul de multiplicare $2^{64}$?
0
Răspunde
Tom avatar
drapel tf
Tom
@garfunkel da, asta e diferit, știu. Am studiat subiectul și am scris propriile mele programe de înmulțire și chiar o funcție de înmulțire GF(2^128) bazată pe modul GCM și instrucțiuni pclmulqdq.
0
Răspunde
drapel ye
garfunkel
@Tom: (Din scrisul tău am crezut că știi și am întrebat doar pentru a fi sigur.) Două diferențe suplimentare între utilizarea modului de multiplicare $2^{16}+1$ (folosind toate elementele câmpului, cu excepția 0) și înmulțirea în câmp cu $2^{16}$ (folosind toate elementele câmpului, inclusiv 0) este că acesta din urmă are întotdeauna 0 ca punct fix și - mult mai important - că acesta din urmă este liniar peste F2 ("xor"), deci lipsește unul esențial proprietatea criptografică S-Box. Așadar, ca și în AES, s-ar putea să trebuiască să utilizați inversarea în câmp cu elemente $2^{64}$.
0
Răspunde
Puncte:0
b degnan avatar Crypto
drapel ca
b degnan

Criptarea, de orice tip, este costisitoare în domeniul hardware și al puterii. Multiplicatorii sunt într-adevăr mari și profundi și, prin urmare, lenți în comparație cu sumatorul complet ALU de bază. Am de gând să fac o grămadă de semne de mână, dar dacă luați o carte de arhitectură CPU, veți găsi următoarele: Designul multiplicatorilor este întotdeauna diferit, dar conducta unității MUL pentru un rezultat pe 64 de biți este 4 -deep, iar pentru un rezultat pe 128 de biți este de 8-deep pe majoritatea procesoarelor. Acest lucru se datorează faptului că utilizați blocuri de adunare pline înlănțuite, iar adâncimea maximă în designul cu 4 adâncimi este de 16. Adâncimea completă a adunării pentru un XOR, ROL sau ADD este echivalentă cu un singur sumator complet. Procesoarele super-scaler ascund o mare parte din întârzierile multiplicatorilor; cu toate acestea, dacă sunteți într-adevăr măcinat de o problemă, veți găsi o conductă goală cu o mulțime de întârzieri.

0 + 0
drapel romania
SEF 777
întrebarea această in alte limbi:

Postează un răspuns

Majoritatea oamenilor nu înțeleg că a pune multe întrebări deblochează învățarea și îmbunătățește legătura interpersonală. În studiile lui Alison, de exemplu, deși oamenii își puteau aminti cu exactitate câte întrebări au fost puse în conversațiile lor, ei nu au intuit legătura dintre întrebări și apreciere. În patru studii, în care participanții au fost implicați în conversații ei înșiși sau au citit transcrieri ale conversațiilor altora, oamenii au avut tendința să nu realizeze că întrebarea ar influența – sau ar fi influențat – nivelul de prietenie dintre conversatori.