Lorsque vous écrivez sur la manière de développer des applications sécurisées, l'un des conseils les plus courants est: n'écrivez pas vous-même la cryptographie, mais utilisez une bibliothèque fiable. Malheureusement, lors du développement de blockchains, ce conseil ne fonctionne souvent pas: les algorithmes requis ne sont pas du tout implémentés ou les implémentations existantes ne conviennent pas pour de nombreuses raisons possibles - même parce qu'elles ne sont pas suffisamment sécurisées . Dans ce cas également , il était nécessaire de vérifier les signatures en utilisant Ed25519 - un type de signatures très populaire pour lequel il existe de nombreuses implémentations, dont aucune ne nous convenait cependant. En effet, la vérification devait être effectuée à partir d'un contrat intelligent s'exécutant sur la blockchain Ethereum.

Qu'est-ce qu'un contrat intelligent

- — , « ». : , , - , , , . - : , , , , - ́ . - - , . , , .

Quel est le problème?

Dans Ethereum, les contrats intelligents sont exécutés dans un environnement spécial - la soi-disant machine virtuelle Ethereum (EVM).

Qu'est-ce que l'EVM

EVM — , -. : , , — , . , , -, .

EVM , , . , , , , , . - . EVM , , , , EVM. EVM-, - Ed25519 — , , , , . , EVM , — Solidity.

EVM diffère considérablement à la fois des architectures de processeurs populaires et des machines virtuelles abstraites couramment utilisées telles que JVM ou WASM. Alors que la plupart des architectures contiennent des opérations permettant de travailler avec des nombres 32 et 64 bits, dans EVM, le seul type de données est un entier de 256 bits. Ceci est très pratique pour l'implémentation d'Ed25519, car tous les calculs nécessaires sont effectués sur des nombres qui correspondent à 256 bits.

Comment fonctionne la signature Ed25519

Ed25519 — Curve25519. $(x, y)$ , $p$ , $2^{255}-19$ — . , , $8\cdot l$ , $l=2^{252}+27742317777372353535851937790883648493$ — . $l$ .

. — , , , — . : — $a$ , — $A=a\cdot G$ ( $G$ — , $l$ ). $a$ , $A$ , , , ( ).

Ed25519 $r$ $R=r\cdot G$ . SHA-512 $R$ , $A$ ( ) : $h=H(R||A||m)$ ( $H$ — -, $||$ , ). $s=r+ha\bmod l$ — . $(R,s)$ . $r$ , , , , .

$h=H(R||A||m)$ , $s\cdot G=R+h\cdot A$ . , . , , , , .

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 .

, .

Cryptographie anormale, ou comment j'ai vérifié les signatures Ed25519 sur Solidity

Quel est le problème?

: - SHA-512

More articles: