Al escribir sobre cómo desarrollar aplicaciones seguras, uno de los consejos más comunes es: no escriba criptografía usted mismo, utilice una biblioteca confiable. Desafortunadamente, al desarrollar blockchains, este consejo a menudo no funciona: los algoritmos requeridos no se implementan en absoluto o las implementaciones existentes no son adecuadas por muchas razones posibles, incluso porque no son lo suficientemente seguras . En este caso, también , fue necesario verificar las firmas usando Ed25519 , un tipo de firmas muy popular para el cual hay muchas implementaciones, ninguna de las cuales, sin embargo, nos convenía. Esto se debe a que la verificación tuvo que realizarse desde un contrato inteligente que se ejecuta en la cadena de bloques Ethereum.

¿Cuál es el problema?

En Ethereum, los contratos inteligentes se ejecutan en un entorno especial: la llamada máquina virtual Ethereum (EVM).

EVM difiere significativamente tanto de las arquitecturas de procesadores populares como de las máquinas virtuales abstractas de uso común, como JVM o WASM. Si bien la mayoría de las arquitecturas contienen operaciones de 32 y 64 bits, en EVM el único tipo de datos es un entero de 256 bits. Esto es muy conveniente para la implementación de Ed25519, ya que todos los cálculos necesarios se realizan en números que encajan en 256 bits.

EVM — . «» , EVM , - . , (gas), , , , . : , . , , 256- , , , . EVM . , , , EVM .

EVM : , (storage). , -. . , , , , . Ed25519 . , , . , Solidity - ( Solidity «» , ). , Solidity (, ), . Solidity JavaScript.

, , JavaScript-, Solidity, Solidity.

: - SHA-512

, Ed25519 — - SHA-512. . EVM -: SHA-256, Keccak-256 ( SHA-3-256), RIPEMD-160, SHA-512 . SHA-512 . EVM — , Solidity . 1024 , 16 . , 16, — , , , .

SHA-512 — :

w[0..15] :=  
for i in 16 .. 79:
    s0 := (w[i-15] ror 1) ^ (w[i-15] ror 8) ^ (w[i-15] >> 7)
    s1 := (w[i-2] ror 19) ^ (w[i-2] ror 61) ^ (w[i-2] >> 6)
    w[i] := w[i-16] + s0 + w[i-7] + s1

a, b, c, d, e, f, g, h := h0, h1, h2, h3, h4, h5, h6, h7
for i in 0 .. 79:
    S0 := (a ror 28) ^ (a ror 34) ^ (a ror 39)
    S1 := (e ror 14) ^ (e ror 18) ^ (e ror 41)
    ch := (e & f) ^ (~e & g)
    maj := (a & b) ^ (a & c) ^ (b & c)
    temp1 := h + S1 + ch + k[i] + w[i]
    temp2 := S0 + maj
    a, b, c, d, e, f, g, h := temp1 + temp2, a, b, c, d + temp1, e, f, g
h0, h1, h2, h3 := h0 + a, h1 + b, h2 + c, h3 + d
h4, h5, h6, h7 := h4 + e, h5 + f, h6 + g, h7 + h

, 16 , , . , : , , , , . : (e & f) ^ (~e & g) (e & (f ^ g)) ^ g, (a & b) ^ (a & c) ^ (b & c) — (a & (b | c)) | (b & c) ( (a & (b ^ c)) ^ (b & c)). : x, x | (x << 64) ( x, 64). , x | (x << 64) .

w[i] w[i-2] (. . w[i-1] ), w ( 256- SIMD). , .

: 16 w, 16 , , . w , , . ( 16 ) , , 4,5 .

: . Curve25519 $$$(x, y)$, : $$$x$ $$$y$, . : $$$y$ , , , $$$x$ . $$$p=2^{255}-19$, 32 . , , $$$x$.

$$$x$ $$$x=\pm\sqrt{(y^2-1)/(dy^2+1)}$. $$$-d$ $$$p$, , , $$$y$. . , . $$$\sqrt{u/v}$, $$$v\ne0$. Ed25519 ( , $$$p\equiv5\pmod8$):

• $$$\beta=uv^3(uv^7)^{(p-5)/8}$.
• $$$v\beta^2=u$, $$$\pm\beta$.
• , $$$v\beta^2=-u$, $$$\pm\sqrt{-1}\beta$.
• , .

? , $$$\beta^8=u^8v^{24}(uv^7)^{p-5}=u^{p+3}v^{7p-11}=(u/v)^4$, , $$$\beta^2=\pm u/v$ $$$\beta^2=\pm\sqrt{-1}u/v$. ( $$$u\ne0$), $$$u/v$ , $$$\sqrt{-1}$ . $$$\beta^2=-u/v$, $$$(\sqrt{-1}\beta)^2=u/v$. , , .

, : $$$\beta=uv^3(uv^7)^{(p-5)/8}$ $$$\beta=u(uv)^{(p-5)/8}$. $$$\beta^8=u^8(uv)^{p-5}=u^{p+3}v^{p-5}=(u/v)^4$, . , $$$v$ $$$v^{2^{250}-1}$ $$$v^{11}$ $$$p$, $$$p$ ( ).

, , $$$sG=R+hA$. , ($$$R$ $$$A$), , , -: $$$sG-hA$, $$$R$. , , — $$$sG-hA$.

. $$$sG$ $$$hA$, . — « » (double-and-add), :

result := 0
for bit_index in n-1 .. 0:
    result := double(result)
    if s & (1<<bit_index) != 0:
        result := add(result, G)
    if h & (1<<bit_index) != 0:
        result := subtract(result, A)

$$$n$ — $$$s$ $$$h$. $$$s$ $$$h$, , $$$G$ ( $$$A$). $$$n$ $$$n$ ( ) , , $$$s$ $$$h$ $$$0$ $$$1$ . . , «» $$$s$ $$$h$, , . , $$$k$ $$$A$ $$$G$ $$$2^k$ $$$2^{k+1}-1$, $$$k+1$ ! :

result := 0
for bit_index in n-1 .. k:
    result := double(result)
    if s & (1<<bit_index) != 0:
        result := add(result, Gmul[s >> (bit_index-k)])
        s := s & ((1 << (bit_index-k)) - 1)
    if h & (1<<bit_index) != 0:
        result := subtract(result, Amul[h >> (bit_index-k)])
        h := h & ((1 << (bit_index-k)) - 1)

, , , $$$k$ . «» $$$s$ $$$h$, . , : $$$k$ . :

• $$$s$ $$$G$ , $$$G$ . $$$s$ $$$2^k$, $$$G$ — $$$2^{-k}\bmod l$. , $$$2^k$ $$$k$ $$$s$ .
• $$$h$ $$$A$ . $$$h$ $$$2^{-k}\bmod l$ $$$2^k$, , $$$A$ $$$l$. $$$A$ $$$l$, $$$(h2^{-k}\bmod l)\cdot2^k$ $$$h$, $$$l$ $$$8l$ ( ), $$$2^{-k}$. , : $$$h$ $$$h+8l-2^k$ ( , $$$h-2^k$ $$$8l$), : result := subtract(result, Amul[(1 << k) + h]), , $$$k$ , $$$2^k$ , $$$A$ $$$2^k$ $$$2^{k+1}-1$.

$$$k=3$, , .

: , . , $$$p$ . EVM , . — Explicit-Formulas Database. , Curve25519. , . , EFD, , , , . : , . , , -2 -4 (. ), , ( ). «madd-2008-hwcd-3» «dbl-2008-hwcd» ( ). , .

-, . (extended projective coordinates) — $$$X$, $$$Y$, $$$Z$ $$$T$, $$$x=X/Z$, $$$y=Y/Z$ $$$xy=T/Z$. , $$$T$ , , — . , , $$$X$, $$$U$, $$$Y$ $$$V$, $$$x=X/U$ $$$y=Y/V$, , ( , $$$T$). $$$X$, $$$U$, $$$Y$, $$$V$, - $$$T$.

-, . madd (mixed addition) — , , . : ; , , . : $$$((y+x)/2, (y-x)/2, xyd)$. (, $$$(y+x, y-x, xy\cdot2d)$, libsodium) 2, EVM , . :

//  :
//  1: (x1, u1, y1, v1), x=x1/u1, y=y1/v1.
//  2: (s2, d2, t2), s2=(y+x)/2, d2=(y-x)/2, t2=x*y*d.
//  :
//  3: (x3, u3, y3, v3), x=x3/u3, y=y3/v3.

//  (x4, y4, z4, t4) -   ,    1,    .
x4 := x1 * v1
y4 := y1 * u1
z4 := u1 * v1
t4 := x1 * y1

//  .  madd-2008-hwcd-3.
s4 := y4 + x4
d4 := y4 - x4
a := d4 * d2 // (y4-x4)*(y2-x2)/2,  A/2.
b := s4 * s2 // (y4+x4)*(y2+x2)/2,  B/2.
c := t4 * t2 //  C/2.
             // D/2 -   z4,   .
x3 := b - a  // E/2.
u3 := z4 + c // G/2.
y3 := b + a  // H/2.
v3 := z4 - c // F/2.
//  x3, u3, y3, v3   E, G, H, F  1/2,    ,    x3/u3  y3/v3   .

:

//  :
//  1: (x1, u1, y1, v1), x=x1/u1, y=y1/v1.
//  :
//  2: (x2, u2, y2, v2), x=x2/u2, y=y2/v2.

//  (x3, y3, z3) -   ,    1,    .  t3  .
x3 := x1 * v1
y3 := y1 * u1
z3 := u1 * v1

//  .  dbl-2008-hwcd.
xx := x3 * x3 // A.
yy := y3 * y3 // B.
xy := x3 * y3 //      E  2xy,   ,  .
zz := z3 * z3
x2 := xy + xy // E.
u2 := yy - xx // G.
y2 := yy + xx // -H.
v2 := zz + zz - u2 // -F.
//  ,  -1   y2  v2     .

: addmod ( ). , $$$2^{255}$, ( ), 256- . , , , . , , .

, . : $$$x=X/U$ $$$y=Y/V$, $$$x$ $$$y$. — ( $$$p-2$), , : $$$(UV)^{-1}$, $$$U^{-1}=(UV)^{-1}V$ $$$V^{-1}=(UV)^{-1}U$. $$$R$, . , . .

, NEAR . - Rust AssemblyScript ( TypeScript) .

, NEAR, -IDE .

, .

!