Marinada '26 - Školjka

Vrijeme: 23:16

Kriptolanac | Cryptochain #5

Diffie-Hellman je metoda za sigurnu razmjenu ključeva preko kanala koji netko može prisluškivati. Osobe A i B međusobno komuniciraju. Prije toga su se dogovorile da koriste isti prosti broj $p$ . Zatim osoba A odabere nasumičan broj $a$ , izračuna $2^a \pmod{p}$ (ostatak pri dijeljenju $2^a$ s $p$ ) i pošalje ga osobi B. Na isti način osoba B odabere nasumično $b$ , izračuna $2^b \pmod{p}$ i pošalje ga osobi A. Osoba A je primila broj $2^b \pmod{p}$ od osobe B i zatim ga potencirala na svoj $a$ , i dalje modulo $p$ , a osoba B učinila je isto s primljenim $2^a \pmod{p}$ i, naravno, svojim $b$ . Nakon ovog postupka obje su strane došle do istog broja $2^{ab} \pmod{p}$ . U to se mogu uvjeriti na razne načine (jedan od njih je da uspostave šifriranu komunikaciju tako da iz tog broja izvedu ključ za šifriranje), a ako ne uspiju, to znači da je netko u komunikacijskom kanalu izmijenio njihove poruke.

Ti si presreo komunikaciju osoba A i B koje su koristile $p = 9155477$ i razmijenile sljedeće poruke:

$A \rightarrow B: 5871180$
$B \rightarrow A: 959697$

Odredi tajni broj $2^{ab} \pmod{p}$ koji su obje osobe izračunale nakon razmjene ključeva!

Diffie-Hellman is a method for securely exchanging keys over a channel that someone may be able to eavesdrop on. People A and B communicate with each other. Beforehand, they agreed to use the same prime number $p$ . Person A then chooses a random number $a$ , calculates $2^a \pmod{p}$ (the remainder when dividing $2^a$ by $p$ ), and sends it to person B. In the same way, person B chooses a random number $b$ , calculates $2^b \pmod{p}$ , and sends it to person A. Person A receives the number $2^b \pmod{p}$ from person B and then raises it to their own power $a$ , still modulo $p$ , while person B does the same with the received $2^a \pmod{p}$ and, of course, their own $b$ . After this procedure, both parties arrive at the same number $2^{ab} \pmod{p}$ . They can verify this in various ways (one of them is to establish encrypted communication by deriving an encryption key from that number), and if they fail, it means that someone in the communication channel has altered their messages.

You intercepted the communication between people A and B, who used $p = 9155477$ and exchanged the following messages:

$A \rightarrow B: 5871180$
$B \rightarrow A: 959697$

Determine the secret number $2^{ab} \pmod{p}$ that both people calculated after the key exchange!

[lang=hr] Diffie-Hellman je metoda za sigurnu razmjenu ključeva preko kanala koji netko može prisluškivati. Osobe A i B međusobno komuniciraju. Prije toga su se dogovorile da koriste isti prosti broj $p$. Zatim osoba A odabere nasumičan broj $a$, izračuna $2^a \pmod{p}$ (ostatak pri dijeljenju $2^a$ s $p$) i pošalje ga osobi B. Na isti način osoba B odabere nasumično $b$, izračuna $2^b \pmod{p}$ i pošalje ga osobi A. Osoba A je primila broj $2^b \pmod{p}$ od osobe B i zatim ga potencirala na svoj $a$, i dalje modulo $p$, a osoba B učinila je isto s primljenim $2^a \pmod{p}$ i, naravno, svojim $b$. Nakon ovog postupka obje su strane došle do istog broja $2^{ab} \pmod{p}$. U to se mogu uvjeriti na razne načine (jedan od njih je da uspostave šifriranu komunikaciju tako da iz tog broja izvedu ključ za šifriranje), a ako ne uspiju, to znači da je netko u komunikacijskom kanalu izmijenio njihove poruke. Ti si presreo komunikaciju osoba A i B koje su koristile $p = 9155477$ i razmijenile sljedeće poruke: $A \rightarrow B: 5871180$\\ $B \rightarrow A: 959697$\\ Odredi tajni broj $2^{ab} \pmod{p}$ koji su obje osobe izračunale nakon razmjene ključeva! [/lang] [lang=en] Diffie-Hellman is a method for securely exchanging keys over a channel that someone may be able to eavesdrop on. People A and B communicate with each other. Beforehand, they agreed to use the same prime number $p$. Person A then chooses a random number $a$, calculates $2^a \pmod{p}$ (the remainder when dividing $2^a$ by $p$), and sends it to person B. In the same way, person B chooses a random number $b$, calculates $2^b \pmod{p}$, and sends it to person A. Person A receives the number $2^b \pmod{p}$ from person B and then raises it to their own power $a$, still modulo $p$, while person B does the same with the received $2^a \pmod{p}$ and, of course, their own $b$. After this procedure, both parties arrive at the same number $2^{ab} \pmod{p}$. They can verify this in various ways (one of them is to establish encrypted communication by deriving an encryption key from that number), and if they fail, it means that someone in the communication channel has altered their messages. You intercepted the communication between people A and B, who used $p = 9155477$ and exchanged the following messages: $A \rightarrow B: 5871180$\\ $B \rightarrow A: 959697$\\ Determine the secret number $2^{ab} \pmod{p}$ that both people calculated after the key exchange! [/lang]