Wenn Sie darüber schreiben, wie sichere Anwendungen entwickelt werden, lautet einer der häufigsten Tipps: Schreiben Sie keine Krypto selbst, sondern verwenden Sie eine vertrauenswürdige Bibliothek. Leider funktioniert dieser Rat bei der Entwicklung von Blockchains oft nicht: Die erforderlichen Algorithmen sind entweder überhaupt nicht implementiert oder die vorhandenen Implementierungen sind aus vielen möglichen Gründen nicht geeignet - auch weil sie nicht sicher genug sind . Auch in diesem Fall war es notwendig, Signaturen mit Ed25519 zu überprüfen - eine sehr beliebte Art von Signaturen, für die es viele Implementierungen gibt, von denen jedoch keine für uns geeignet war. Dies liegt daran, dass die Überprüfung anhand eines intelligenten Vertrags durchgeführt werden musste, der in der Ethereum-Blockchain ausgeführt wird.

Was ist ein kluger Vertrag?

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

Worin besteht das Problem?

In Ethereum werden intelligente Verträge in einer speziellen Umgebung ausgeführt - der sogenannten Ethereum Virtual Machine (EVM).

Was ist EVM?

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

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

EVM unterscheidet sich sowohl von gängigen Prozessorarchitekturen als auch von häufig verwendeten abstrakten virtuellen Maschinen wie JVM oder WASM erheblich. Während die meisten Architekturen Operationen zum Arbeiten mit 32- und 64-Bit-Zahlen enthalten, ist in EVM der einzige Datentyp eine 256-Bit-Ganzzahl. Dies ist sehr praktisch für die Implementierung von Ed25519, da alle erforderlichen Berechnungen für Zahlen durchgeführt werden, die in 256 Bit passen.

So funktioniert die Ed25519-Signatur

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 .

, .

Abnormale Kryptographie oder wie ich Ed25519-Signaturen auf Solidity verifiziert habe

Worin besteht das Problem?

: - SHA-512

More articles: