Puncte:0

Decriptarea unui text cifrat în criptosistemul ElGamal

drapel fr

Sunt student la informatică, lucrând în prezent la o problemă stabilită în criptografie (problemă practică, dar blocată la partea de matematică).

Practic, să presupunem că primim un mesaj care a fost criptat folosind sistemul cripto al ElGamal și scopul nostru este să decriptăm și să recuperăm complet mesajul.

Textul simplu inițial este o secvență $p_1p_2\ldots p_m$. Ni se oferă o versiune hashing a cheii publice SHA256$(g^s)$ (asa de $s$ este cheia privată și $g^s$ cea publică). Pentru criptare, se spune că an $r_1$ valoarea este eșantionată uniform la întâmplare și apoi pentru o anumită valoare dată $u\in\mathbb{Z}_q$, $r_i=u^{i-1}r_1$ pentru tot restul $i$lui. Textul cifrat este atunci $c_i=(g^{r_i},p_ig^{r_is})_{i\in[m]}$.

În general, ni se oferă $p$, $q$, $g$, $u$, cheia publică codificată $H$ și textul cifrat $c_i$ ca un tuplu.

Problema pe care o am este că nu văd cu adevărat ce calcule trebuie să facem pentru a recupera întreaga secvență originală. Unul dintre asistenți mi-a spus să găsesc câteva $p_i$și apoi le folosesc pentru a decripta cifrul, dar nu văd unde mă duce asta. The $r$Sunt necunoscute și chiar dacă știm $g^{r_i}$, deoarece ni se dau valori destul de uriașe, nu putem calcula jurnalul.

Sunt puțin pierdut aici, să fiu sincer (nu am o experiență enormă în algebră), așa că dacă cineva are un sfat despre ce ar trebui să fac, aș aprecia cu adevărat.

Mulțumiri :)

yacovm avatar
drapel us
Dar cheia privată nu este $s$? Nu poți ridica $g^{r_i}$ la $s$ ca în schema obișnuită?
seboll13 avatar
drapel fr
@yacovm da $s$ este cheia privată, dar nu o știm, așa că nu putem face niște calcule cu ea. Bănuiesc că cea mai bună soluție ar fi cumva să găsești o modalitate de a ști $r_1$, dar nu știu cum.
kelalaka avatar
drapel in
Ai putea să citești mai întâi https://en.wikipedia.org/wiki/ElGamal_encryption apoi să ne spui unde ai eșuat?
yacovm avatar
drapel us
Deci încerci să decriptezi fără să cunoști cheia privată? Asta e sarcina?
seboll13 avatar
drapel fr
Bănuiesc că încep să cred că ne lipsesc unele elemente cruciale din enunțul problemei (chiar dacă nu este cazul). Într-adevăr @yacovm nu avem acces la cheia privată $s$. Avem acces doar la un hash de $g^s$. AT ne-a spus să ghicim niște $p_i$, dar nu prea văd cum să facem asta.
seboll13 avatar
drapel fr
@kelalaka Presupun că în scenariul nostru trebuie să procedăm puțin diferit față de modul în care funcționează procesul real de decriptare, de aceea sunt parțial confuz :p
fgrieu avatar
drapel ng
Care este dimensiunea lui $p$, în biți sau cifre zecimale? Dacă este suficient de mic, pot exista atacuri. De asemenea, este $(p-1)/2$ prim sau un compus cu factori non-triviali?
seboll13 avatar
drapel fr
@fgrieu $p$ este o putere a doi, mai exact este $2^{1024}$, deci 309 de cifre. Dacă nu mă înșel, $(p-1)/2$ nu este prim. Cred că sunt aproape de ceva, dar calculele cu modulos sunt întotdeauna destul de provocatoare.
fgrieu avatar
drapel ng
Dacă $p$ este o putere mare de doi, nu este prim, iar $(p-1)/2$ nu poate fi prim. Ești sigur de asta?
fgrieu avatar
drapel ng
Ignorând ceea ce ați spus despre $p$: cred că miezul problemei este că $r_i$ nu sunt aleatorii, așa cum ar trebui. Doar pentru a verifica dacă am înțeles corect ecuațiile: ar trebui să puteți verifica că $g^{r_i}=(g^{r_1})^{(u^{i-1})}\bmod p$ (observați că $g^{r_i}$ sunt prima parte a textelor cifrate). Acum faceți ceva similar cu a doua parte a textelor cifrate și ar trebui să puteți obține toate $p_i/p_1\bmod p$. Și apoi..
seboll13 avatar
drapel fr
@fgrieu Sunt sigur că p nu este prim (asta e banal) și destul de sigur că (p-1)/2 este. Mă voi uita la ceea ce spui. Dar pentru a clarifica: $r_1$ este aleatoriu, $u$ este de asemenea (uniform aleatoriu în $\mathbb{Z}_q$ și toate $r_i$â-urile rămase sunt generate pe baza $r_1$ și $u precedente $. Deci trucul cred că este să găsești cumva niște $r_i$ și să mergi mai departe de acolo.
Puncte:0
drapel tr

Ar trebui să încerci să găsești $r_{1}$. Pentru aceasta, încercați să vedeți dacă există o relație între $c_{i}$ și $c_{j}$, mai ales între $g^{r_{i}}$ și $g^{r_{j}}$. Poate găsiți o $c$ astfel încât $g^{c}=g^{r_{i}}/g^{r_{j}}$. Apoi puteți calcula $g^{s}$

seboll13 avatar
drapel fr
Vă mulțumesc pentru răspunsul dvs. :) da, acesta a fost scopul meu principal, de fapt, găsirea unui singur $r_i$ este suficientă aici pentru că de acolo putem găsi cu ușurință $r_1$ și orice altceva. Dar, calculele cu modulos sunt destul de complicate, așa că fac tot posibilul să lucrez la asta și să găsesc o soluție.

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.