Dlaczego mnożenie kluczy publicznych przez siebie jest niezdefiniowane w ECDSA?

Idąc śladami vjudeu i próbując pisać w podobnym stylu, wrzucam swoje tłumaczenie. Myślę, że to dobry początek, zanim w ogóle przejdziemy do sygnatur Schnorra.

Wielu ludzi zastanawia się, dlaczego nie możemy mnożyć kluczy publicznych przez siebie w ECDSA. Możemy dodawać punkty na krzywej eliptycznej, odejmować je, mnożyć punkt przez jakąś liczbę, czy też wykonywać analogiczne dzielenie (wykorzystując inwersję). Głównym powodem takiego stanu rzeczy jest ukryty argument, o którym często się zapomina: punkt bazowy.

Bardzo często ludzie myślą o takich rzeczach, jak "dzielenie punktu na pół" w podobny sposób, w jaki można to zrobić na liczbach całkowitych, w innych językach programowania: jeśli mamy 9/10, to nam daje zero jako wynik. W przypadku ECDSA, takie reguły nie działają.

Aby lepiej zrozumieć, jak mnożenie punktu przez punkt mogłoby być zdefiniowane, możemy wziąć krzywą eliptyczną, którą kiedyś miałem w swoim awatarze: "p=79,n=67,base=(1,18),bits=7". Całość wygląda dość prosto, każda współrzędna zajmuje tylko jeden bajt i możemy z łatwością w pełni prześledzić wszystko, co tam się dzieje, bez dodawania jakichkolwiek optymalizacji, zwyczajnie sprawdzając wszystko metodą brute-force.

Zatem, zaczynamy od naszego p=79. Możemy łatwo ustalić, że mamy do czynienia z liczbą pierwszą, a także znaleźć najbliższy punkt, spełniający słynne równanie: y^2=x^3+7. Wszystkie liczby są na tyle małe, że możemy łatwo utworzyć bitmapę o rozmiarach 79x79 z czarnym tłem, a następnie ustawić białe piksele w miejscach, w których pozycja (x,y) spełnia wcześniej podane równanie. Co więcej, możemy nawet spróbować zrobić to samo, używając nieco większych liczb, uzyskując piękną tapetę, przypominającą gwiazdy na nocnym niebie.

Ciekawostka od tłumacza: użytkownik vjudeu w międzyczasie opublikował na swoim GitHubie pliki PNG z wszystkimi takimi krzywymi eliptycznymi, gdzie p<1000: https://github.com/vjudeu/curves1000

W ten sposób, możemy łatwo znaleźć najbliższy punkt, wynoszący (1,18) w tym przypadku. Dodatkowo, możemy policzyc wszystkie kropki i zauważyć, że mamy 66 punktów, zaś 67. wartość wynosi po prostu (0,0) i jest punktem w nieskończoności (który możemy uzyskać później, gdy spróbujemy dodać do siebie pierwszy i ostatni punkt).

Zatem, zacznijmy od punktu bazowego i utwórzmy listę wszystkich punktów:

Code:

d= 1, x= 1, y=18
d= 2, x=60, y=10
d= 3, x=15, y= 8
d= 4, x=49, y= 5
d= 5, x=42, y=54
d= 6, x=59, y=12
d= 7, x=61, y=10
d= 8, x=43, y=35
d= 9, x=37, y=69
d=10, x=26, y=19
d=11, x=18, y=54
d=12, x=12, y=47
d=13, x=39, y=47
d=14, x= 9, y= 5
d=15, x=63, y=63
d=16, x=19, y=25
d=17, x=75, y=41
d=18, x=21, y=74
d=19, x=68, y=63
d=20, x=29, y= 8
d=21, x= 6, y=12
d=22, x=45, y=19
d=23, x=35, y=71
d=24, x=66, y=41
d=25, x=28, y=32
d=26, x=17, y=41
d=27, x=14, y=67
d=28, x=74, y=35
d=29, x=23, y=18
d=30, x=55, y=61
d=31, x=41, y=35
d=32, x= 8, y=60
d=33, x=27, y=63
d=34, x=27, y=16
d=35, x= 8, y=19
d=36, x=41, y=44
d=37, x=55, y=18
d=38, x=23, y=61
d=39, x=74, y=44
d=40, x=14, y=12
d=41, x=17, y=38
d=42, x=28, y=47
d=43, x=66, y=38
d=44, x=35, y= 8
d=45, x=45, y=60
d=46, x= 6, y=67
d=47, x=29, y=71
d=48, x=68, y=16
d=49, x=21, y= 5
d=50, x=75, y=38
d=51, x=19, y=54
d=52, x=63, y=16
d=53, x= 9, y=74
d=54, x=39, y=32
d=55, x=12, y=32
d=56, x=18, y=25
d=57, x=26, y=60
d=58, x=37, y=10
d=59, x=43, y=44
d=60, x=61, y=69
d=61, x=59, y=67
d=62, x=42, y=25
d=63, x=49, y=74
d=64, x=15, y=71
d=65, x=60, y=69
d=66, x= 1, y=61
d=67, x= 0, y= 0
d=68, x= 1, y=18

Po obsłużeniu skrajnych przypadków, możemy zamienić każdy klucz prywatny "d" na odpowiednią parę (x,y) i kręcić się tak w nieskończoność:

Code:

(1,18)+(1,61)=(0,0)
(1,18)+(0,0)=(1,18)

Jak łatwo zauważyć, zaczęliśmy od p=79 oraz równania y^2=x^3+7, nie mieliśmy żadnych innych danych wejściowych. Uzyskaliśmy n=67 i w tym momencie możemy mieć 100% pewności, że wartość "n" to nie jest coś, co wybieramy, tylko po prostu obliczamy. To jedyny prawidłowy wynik, dzięki czemu całość może działać prawidłowo i spełnia nasze kryteria bycia "tak podobnym do secp256k1, jak to tylko możliwe" używając mniejszych liczb w celu pokazania, jak to wszystko ze sobą współgra. Jeśli zwiększymy liczby, możemy nabrać jeszcze większej pewności, że wartość "n" nie została wybrana ręcznie: po prostu została wyliczona, używając świetnie zoptymalizowanego kodu.

Ciekawostka od tłumacza: przykłady większych krzywych eliptycznych są w jednym z anglojęzycznych tematów: https://bitcointalk.org/index.php?topic=5459153

Teraz już mamy wszystko, czego potrzebujemy, aby dowiedzieć się, dlaczego nie możemy mnożyć dwóch kluczy publicznych przez siebie. Zapiszmy parę mnożeń na kluczach prywatnych i zamieńmy je na odpowiednie klucze publiczne, zgodnie z tabelą wyżej:

Code:

 2* 3= 6
 5* 7=35
11*13=35 (mod 67)

(60,10)*(15, 8)=(59,12)
(42,54)*(61,10)=( 8,19)
(18,54)*(39,47)=( 8,19)

W tym momencie, możemy spróbować założyć, że chcemy używać innego punktu bazowego, na przykład (75,41) zamiast (1,18). Utwórzmy pełną listę wszystkich punktów i zobaczmy, jak nagle wszystko zacznie się zmieniać:

Code:

d= 1, x=75, y=41
d= 2, x=27, y=16
d= 3, x=19, y=54
d= 4, x= 1, y=18
d= 5, x=21, y=74
d= 6, x= 8, y=19
d= 7, x=63, y=16
d= 8, x=60, y=10
d= 9, x=68, y=63
d=10, x=41, y=44
d=11, x= 9, y=74
d=12, x=15, y= 8
d=13, x=29, y= 8
d=14, x=55, y=18
d=15, x=39, y=32
d=16, x=49, y= 5
d=17, x= 6, y=12
d=18, x=23, y=61
d=19, x=12, y=32
d=20, x=42, y=54
d=21, x=45, y=19
d=22, x=74, y=44
d=23, x=18, y=25
d=24, x=59, y=12
d=25, x=35, y=71
d=26, x=14, y=12
d=27, x=26, y=60
d=28, x=61, y=10
d=29, x=66, y=41
d=30, x=17, y=38
d=31, x=37, y=10
d=32, x=43, y=35
d=33, x=28, y=32
d=34, x=28, y=47
d=35, x=43, y=44
d=36, x=37, y=69
d=37, x=17, y=41
d=38, x=66, y=38
d=39, x=61, y=69
d=40, x=26, y=19
d=41, x=14, y=67
d=42, x=35, y= 8
d=43, x=59, y=67
d=44, x=18, y=54
d=45, x=74, y=35
d=46, x=45, y=60
d=47, x=42, y=25
d=48, x=12, y=47
d=49, x=23, y=18
d=50, x= 6, y=67
d=51, x=49, y=74
d=52, x=39, y=47
d=53, x=55, y=61
d=54, x=29, y=71
d=55, x=15, y=71
d=56, x= 9, y= 5
d=57, x=41, y=35
d=58, x=68, y=16
d=59, x=60, y=69
d=60, x=63, y=63
d=61, x= 8, y=60
d=62, x=21, y= 5
d=63, x= 1, y=61
d=64, x=19, y=25
d=65, x=27, y=63
d=66, x=75, y=38
d=67, x= 0, y= 0
d=68, x=75, y=41

Następnie, zapiszmy ponownie te same mnożenia:

Code:

 2* 3= 6
 5* 7=35
11*13=35 (mod 67)

(27,16)*(19,54)=( 8,19)
(21,74)*(63,16)=(43,44)
( 9,74)*(29, 8)=(43,44)

Widzicie? Wszystko wygląda zupełnie inaczej. Wszystko się zmieniło. Możemy nawet wziąć nasze stare punkty i zobaczyć, jakie klucze prywatne się za nimi kryją, gdy weźmiemy pod uwagę nasz nowy punkt bazowy:

Code:

(60,10)*(15, 8)=(59,12)
(42,54)*(61,10)=( 8,19)
(18,54)*(39,47)=( 8,19)

8*12=24
20*28=6
44*52=6

Widzicie? Mnożenie dwóch kluczy publicznych przez siebie prowadzi do kompletnie błędnych wyników, jeśli próbujemy robić to bezpośrednio, na podstawie dwóch punktów, bez obliczania wszystkiego względem punktu bazowego. Mam nadzieję, że ten temat pozwoli lepiej zrozumieć, dlaczego niektóre działania nie mogą być wykonane w ramach ECDSA, a także jak niejawne argumenty, takie jak punkt bazowy, mogą łatwo zmienić wszystko, jeśli zapomnimy ich uwzględnić w naszych obliczeniach.