Puncte:1

Schimbarea cheilor secrete, n și m manual cu forța brută a schimbului de chei Diffie-Hellman

drapel us

Problemă: vezi că Michael și Nikita convin asupra unei chei secrete folosind schimbul de chei Diffie-Hellman. Michael și Nikita aleg $p = 97$ și $g = 5$. Nikita alege un număr aleator n și îi spune lui Michael asta $g^n \equiv 3\pmod{97}$, iar Michael alege un număr aleatoriu $m$ și îi spune lui Nikita acea $g^m â¡ 7 \pmod{97}$. Forța brută sparge codul lor: Ce este cheia secretă asupra căreia Nikita și Michael sunt de acord? Ce este $n$? Ce este $m$?

Acesta este modul în care schimbul Diffie-Hellman este definit în manual:

  1. Împreună, Michael și Nikita aleg un număr întreg de 200 de cifre p care este probabil pentru a fi prim și alegeți un număr $g$ cu $1 < g < p$.
  2. Nikita alege în secret un număr întreg $n$.
  3. Michael alege în secret un număr întreg $m$.
  4. Nikita calculează $g^n \pmod{p}$ pe computerul ei portabil și spune Michael numărul rezultat la telefon.
  5. îi spune Michael Nikitei $g^m \pmod{p}$.
  6. Cheia secretă partajată este atunci $s\equiv g^{nm}\pmod{p}$ pe care atât Nikita cât și Michael le pot calcula.

Gândurile/încercările mele:
Încercarea 1. Am încercat să găsesc $n$ prin rezolvarea ecuaţiei modulare $5^n\equiv 3\pmod{97}.$ Atunci noi avem $n\equiv \log_53\pmod{97},$ care nu este un număr întreg și, prin urmare, nu are sens.
Încercarea 2. Am încercat să găsesc cheia folosind $g^n$ și $g^m.$ Cu toate acestea, nu văd o cale de a ajunge $g^{nm}$ de cand $g^ng^m = g^{n+m},$ și nu putem calcula $(g^n)^m$ sau $(g^m)^n$ fara sa stie $m$ sau $n,$ pentru care din Incercarea 1 nu gasesc numere intregi pentru.

Ar aprecia ajutor! Mulțumesc

DannyNiu avatar
drapel vu
Încercarea 1 este pe drumul cel bun. Trebuie remarcat faptul că, logaritmul este discret, astfel încât funcția de jurnal al numărului real nu este aplicabilă aici. Ar trebui să fie un număr întreg și, așa cum ați spus, altfel nu are sens.
BoostMatch avatar
drapel us
Cum o poți rezolva dacă este un jurnal discret?
DannyNiu avatar
drapel vu
Forța brutală (încercarea una câte una) este bună pentru numere mici de genul acesta din exercițiul tău. Hackerii ar folosi tehnici matematice, cum ar fi Pollard-rho sau sita generală a câmpului numeric (GNFS).
BoostMatch avatar
drapel us
@DannyNiu Oh, de aici „forța brută” din exercițiu!
kelalaka avatar
drapel in
Cu un mic program în timp ce construiți [tabelul index](https://crypto.stackexchange.com/a/76241/18298), găsiți valoarea dorită.

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.