Încerc să fac un modul RSA în VHDL, care la rândul său va fi implementat pe un FPGA. Încerc să implementez un algoritm Montgomery complet, ceea ce înseamnă că lucrez cu algoritmul Montgomery Exponetiation și algoritmul Montgomery Multiplication. În cea mai mare parte, testele mele constau în generarea de numere aleatorii (chei, modul, r, mesaje) pe care le folosesc pentru a efectua criptarea/decriptarea. Dacă mesajul original este egal cu mesajul decriptat, testul a trecut.
Mai întâi am făcut un cod de nivel înalt al versiunii la nivel de biți a Montgomery Multiplication în Python. În timp ce încercam să scap de scăderea finală am găsit acest postare de Brett pe Stack Overflow. A făcut și o postare Aici cam acelasi lucru. Acest lucru m-a ajutat să fac ca algoritmul la nivel de biți să funcționeze în Python fără scădere finală. În plus, părea să funcționeze în VHDL atunci când se efectuează simulări.
Următorul a fost să facem ca algoritmul la nivel de cuvânt să funcționeze. Citind documentul c03gfp de Ãetin Kaya Koç găsit Aici, am reușit să fac ca codul Python de nivel înalt al algoritmului la nivel de cuvânt să funcționeze, dar nu așa cum am sperat, așa cum a trebuit să păstrez scăderea finală.Folosirea aceluiași R care a fost folosit în codul la nivel de biți nu a funcționat pentru codul la nivel de cuvânt. Sincer, nu sunt sigur dacă Brett întreabă despre același lucru Aici, dar ar putea fi.
Am încercat să găsesc documente care descriu cum ar trebui făcut acest lucru, în principal prin căutarea pe google, dar nu am avut noroc să găsesc. Dacă am găsit vreunul care ar putea să mă ajute să scap de scăderea finală din algoritmul la nivel de cuvânt, nu am înțeles conținutul documentelor în acel caz.
Am avut o idee că aș putea încerca să măresc R-ul mai mult decât ceea ce s-a făcut atunci când am folosit optimizarea Walter pentru algoritmul la nivel de biți. Având în vedere că lucrez cu la nivel de cuvânt algoritm, de ce să nu fie R cu un cuvânt mai lat decât modulul?
Pentru algoritmul la nivel de biți pe care l-am setat R = 2^(2 * NUM_BITS) mod n după cum sugerează Renaud Pacalet, Unde NUM_BITS = 256 + 2 în cazul meu, deoarece lucram cu numere de 256 de biți.
Pe de altă parte, pentru algoritmul la nivel de cuvânt, am încercat să setez R = 2^(2 * (NUM_BITS + WORD_WIDTH)) mod n. În cazul meu NUM_BITS = 256 și WORD_WIDTH = 32, dar WORD_WIDTH ar putea fi, de asemenea, 8, 16, 64 sau 128, de exemplu (rețineți că WORD_WIDTH $\leq$ NUM_BITS). Acest lucru a funcționat și a funcționat pentru toate testele pe care le-am efectuat în Python cu numere aleatorii. Încă nu am implementat acest lucru în VHDL, deoarece aș dori să verific dacă acest lucru este corect înainte de a face acest lucru, sau cel puțin să am mai multe baze pentru a face acest lucru.
Deci întrebarea mea este dacă setarea este corectă R = 2^(2 * (NUM_BITS + WORD_WIDTH)) mod n pentru înmulțirea Montgomery la nivel de cuvânt așa cum am făcut-o acum.
De asemenea, există documente care descriu acest lucru?
EDITARE 1
Se pare că după ce mi-am reformulat întrebarea în timp ce căutam pe Google, am dat peste acest post de Saf. Răspunsul oferit de Thomas Pornin pare să aproape răspunde la întrebarea mea, deoarece întrebarea mea a fost în esență aceeași întrebare cu cea pe care a pus-o Saf.
Thomas Pornin a scris că dacă modulul $n$ are o dimensiune de NUM_BITS, atunci ar fi trebuit să caut următorul multiplu al WORD_WIDTH.
Repetând exemplul Thomas Pornins unde WORD_WIDTH = w = 32:
Pentru un modul de 1024 de biți, care este deja un multiplu de 32, utilizați $R=2^{1024}$. Pentru un modul de 1025 de biți, ați folosi $R=2^{1056}$.
Acesta nu pare să fie cazul pentru mine decât dacă am înțeles greșit ceva. Prin testarea mea cu NUM_BITS = 256 și WORD_WIDTH = 32 Am găsit acea setare $R=2^{256}$ ar putea eșuează chiar dacă $n$ este un număr de 256 de biți și chiar dacă $n$ este un număr de 255 de biți. Pe de altă parte, testele au întotdeauna succes când $R=2^{256 + 32\cdot c}$, Unde $c$ este un număr întreg pozitiv. Am testat doar cu $c = [1,2,3]$, așa că nu pot garanta că toate numerele pozitive vor funcționa. De asemenea, ar trebui să se ia în considerare calitatea testelor mele și câte am efectuat ($+1000000$).
Următoarele sunt, de asemenea, răspunsul lui Thomas Pornins la întrebarea lui Safs:
Cazul este că înmulțirea Montgomery are sens numai cu dimensiunile cuvintelor. Cu $w$ ca dimensiunea cuvântului, atunci $R=2^{kw}$ pentru un număr întreg k, care ar trebui să fie ales cât mai mic posibil, având în vedere că $R\ge N$.
Mie mi se pare $R > N$ ar trebui să fie cazul. Ceva comentarii despre asta?
