Algorytmy kryptograficzne | Laboratorium 11

Niech $E$ będzie krzywą eliptyczną nad $\mathbb{Z}_{17}$ o równaniu $$ E\colon y^2 = x^3 + 2x + 2 $$

• Wyznacz wszystkie punkty, które należą do $E$.
• Dla $P=(5,1)$ i $Q=(6,3)$ oblicz $-P$, $P+Q$, $P-Q$, $2P$, $3P$, $7P$.
• Zaimplementuj podstawową arytmetykę na krzywej $E$ nad $\mathbb{Z}_{17}$: dodawanie punktów, podwajanie i mnożenie przez liczbę naturalną. Dla $G = (5,1)$ oblicz $$ 2G,\quad 4G,\quad 8G,\quad 9G,\quad 11G $$ oraz wyznacz rząd punktu $G$.

Możesz korzystać z gotowych wzorów: Elliptic curve point multiplication.

Niech $E$ będzie krzywą eliptyczną nad $\mathbb{Z}_{17}$ daną równaniem $$ E\colon y^2 = x^3 + 2x + 2. $$ Ustalmy generator $G=(5,1)$.

• Wykonaj dwie niezależne sesje protokołu Diffiego–Hellmana i wygeneruj klucz (wspólny sekret) dla Alicji i Boba.
  • Sesja 1: $a=5$, $b=7$.
  • Sesja 2: $a=9$, $b=13$.
• Bob otrzymał (w niezależnych sesjach) od Alicji punkty $A_1=(9,2)$, $A_2=(0,6)$, $A_3=(13,10)$, $A_4=(16,5)$. Które może przyjąć jako klucz publiczny na tej krzywej?

Niech $E$ i $G$ będą jak w zadaniach 1 i 2. Bob ma klucz prywatny $d=3$, a wiadomości są punktami na $E$.

• Wyznacz klucz publiczny $Q=dG$.
• Dla $M_1=(6,3)$ i $M_2=(10,6)$ (przy tym samym $k=5$) wyznacz szyfrogramy $(C_1, C_2^{(1)})$ oraz $(C_1, C_2^{(2)})$.
• Znając $M_1$ i oba szyfrogramy, odzyskaj $M_2$.
• Odszyfruj szyfrogram $C_1=(9,16)$, $C_2=(6,14)$.