In questo post aggiungo qualche dettaglio anche pratico di calcolo sugli elementi di Fp, il campo delle coordinate che può essere visto (come tutti i campi finiti) sia come gruppo additivo che come gruppo moltiplicativo (tolto lo zero).
Poichè nel nostro caso Fp = Zp (campo delle classi dei resti della divisione degli interi per p), si ha che:
a) Fp è un gruppo ciclico di ordine p rispetto all'operazione di addizione
b) Fp - {0} è un gruppo ciclico di ordine p -1 rispetto all'operazione di moltiplicazione (si può dimostrare)
quindi per
a) si ha che a+a+a+a+a+a... = a*p = 0 mod p per ogni a di Fp
b) si ha che a*a*a*a*a ........... = a^(p-1) = 1 mod p per ogni a di Fp - {0}
La seconda relazione è quella che ci interessa.
Già Fermat aveva dimostrato un risultato pressochè equivalente:
per ogni numero primo p è sempre vera la relazione a^p - a = multiplo di k, ovvero a^p = a mod p (piccolo teorema di Fermat)
1) Visto che il campo finito Fp è un gruppo ciclico (rispetto all'operazione di moltiplicazione) di ordine p - 1, si può utilizzare la relazione precedente per calcolare l'inverso di un elemento a diverso da 1:
a^(p-1) = 1 mod p (a^(ordine) = 1)
quindi
a^(p-1) * a^(-1) = 1 * a^(-1) = a^(-1) mod p
Quindi a^(p-2) = a^(-1) mod p
Ad esempio per calcolare l'inverso di 4 in F_ 7 basta fare 4^(7-2) = 2 mod 7 e infatti 4*2 = 1 mod 7 (effettivamente 2 è l'inverso di 4 in F_7).
Sia nella mia prima versione della libreria micro_ecdsa che nella libreria secp256k1 si utilizza questo metodo (ovviamente nella libreria secp256k1 c'è un'ottimizzazione per la quale si è riusciti a minimizzare il numero di moltiplicazioni necessarie per ottenere a^(p-2) ricorrendo agli elevamenti al quadrato, un po' come nel caso della moltiplicazione (addizione ripetuta) per uno scalare si utilizzano i raddoppi dei punti per fare meno addizioni possibili.
2) E' possibile anche ricavare la radice quadrata di b = a^2.
Infatti se p = 3 mod 4 (come succede effettivamente nella secp256k1), allora p + 1 è un multiplo di 4, e quindi:
a^p = a mod p
a^(p+1) = a^2 mod p
a^((p+1)/4) = a^1/2 = sqrt(a) mod p
Code:
>>> p = 0xfffffffffffffffffffffffffffffffffffffffffffffffffffffffefffffc2f
>>> p % 4
3
>>> a = 0x79be667ef9dcbbac55a06295ce870b07029bfcdb2dce28d959f2815b16f81798
>>> a1 = pow(a, (p+1)/4, p) #sqrt(b)
>>> print(hex(a1))
0xcb6dfbd6cdf31164bbeb3052460c1fa3f827f01d6e7fb5f69580cfb96560c16a
>>> (a1 * a1)-a % p #verifica
0
>>> a2 = p-a #a2 = -a1 trovo l'altra radice
>>> print(hex(a2))
0x34920429320cee9b4414cfadb9f3e05c07d80fe291804a096a7f30459a9f3ac5
>>> (a2 * a2)-a % p #verifica
0
>>> p % 4
3
>>> a = 0x79be667ef9dcbbac55a06295ce870b07029bfcdb2dce28d959f2815b16f81798
>>> a1 = pow(a, (p+1)/4, p) #sqrt(b)
>>> print(hex(a1))
0xcb6dfbd6cdf31164bbeb3052460c1fa3f827f01d6e7fb5f69580cfb96560c16a
>>> (a1 * a1)-a % p #verifica
0
>>> a2 = p-a #a2 = -a1 trovo l'altra radice
>>> print(hex(a2))
0x34920429320cee9b4414cfadb9f3e05c07d80fe291804a096a7f30459a9f3ac5
>>> (a2 * a2)-a % p #verifica
0
Questa è l'implementazione di questa funzione nella libreria secp256k1. In quella libreria quando ci si riferisce a un'operazione definita su un elemento del campo delle coordinate si usa la sillaba 'fe' = field element , quando invece ci si riferisce a un'operazione sui punti della curva si usa la sillaba 'ge' = group element come succede ad esempio qui nell'implementazione della funzione che somma due punti della curva.
:
