class Ed25519Keccak::Ed25519Base
base class of Ed25519
Public Class Methods
# File lib/ed25519_keccak/ed25519base.rb, line 7 def initialize( hash_function ) @hash_function = hash_function end
Public Instance Methods
calculate public key from secret
# File lib/ed25519_keccak/ed25519base.rb, line 22 def secret_to_public(secret, form=:byte) publickey = p_secret_to_public( change_argument_format(secret, form) ) return change_result_format( publickey, form ) end
# File lib/ed25519_keccak/ed25519base.rb, line 11 def sign(secret, message, form=:byte) arguments = change_arguments_format( [secret,message], form ) return change_result_format( p_sign(*arguments), form) end
# File lib/ed25519_keccak/ed25519base.rb, line 16 def verify(public_key, message, signature, form=:byte) arguments = change_arguments_format( [public_key,message,signature], form ) return p_verify(*arguments) end
Private Instance Methods
# File lib/ed25519_keccak/ed25519base.rb, line 66 def bytes_to_hexstr( binary ) return binary.unpack("H*").first end
Argument is always changed to a byte-string if specified format is unknown, data is not changed. format type is symbol
# File lib/ed25519_keccak/ed25519base.rb, line 33 def change_argument_format( argument , form ) case form when :hex then return hexstr_to_bytes(argument) end # Other than those above : no change return argument end
# File lib/ed25519_keccak/ed25519base.rb, line 42 def change_arguments_format( arguments, form ) result = [] arguments.each{ |argument| result.push( change_argument_format( argument, form) ) } return result end
result_data is always byte-string
# File lib/ed25519_keccak/ed25519base.rb, line 49 def change_result_format( result_data, form ) case form when :hex then return bytes_to_hexstr(result_data) end # Other than those above : no change return result_data end
region hash function ##
# File lib/ed25519_keccak/ed25519base.rb, line 90 def hash512(s) return @hash_function.call(s) end
calculate Hash(s) modp
# File lib/ed25519_keccak/ed25519base.rb, line 119 def hash512_modq(s) return int_form_bytes(hash512(s)) % @@q end
region common util ##
# File lib/ed25519_keccak/ed25519base.rb, line 61 def hexstr_to_bytes( hex_str ) raise ArgumentError , "hex-string length should be even" if hex_str.length.odd? return [hex_str].pack("H*") end
convert byte-string to int (read bytes in little endian)
# File lib/ed25519_keccak/ed25519base.rb, line 83 def int_form_bytes(b) return bytes_to_hexstr(b.reverse).to_i(16) end
convert int to byte-string (littleEndian) num : unsigned number to convert to bytes length : byte length
# File lib/ed25519_keccak/ed25519base.rb, line 73 def int_to_bytes( num , length ) raise ArgumentError , "num :" + num.to_s if num < 0 raise ArgumentError , "length :" + length.to_s if length < 0 hex_str = num.to_s(16) hex_str = hex_str.rjust(length*2,"0") return hexstr_to_bytes(hex_str).reverse[0,length] end
calculate 1/x modp
# File lib/ed25519_keccak/ed25519base.rb, line 113 def modp_inv(x) return pow_mod(x , @@p-2 , @@p) end
public_keyKey = aG “a” is generated form a secret
# File lib/ed25519_keccak/ed25519base.rb, line 278 def p_secret_to_public(secret) expanded = secret_expand(secret) a = expanded.first return point_compress(point_mul(a, @@G)) end
- signature format
-
| compressed data of _R | s | <- concatnate
# File lib/ed25519_keccak/ed25519base.rb, line 244 def p_sign(secret, message) a, prefix = secret_expand(secret) _A = point_compress(point_mul(a, @@G)) r = hash512_modq(prefix + message) _R = point_mul(r, @@G) _Rs = point_compress(_R) h = hash512_modq(_Rs + _A + message) s = (r + h * a) % @@q return _Rs + int_to_bytes(s,32) end
# File lib/ed25519_keccak/ed25519base.rb, line 255 def p_verify(public_key, message, signature) # check arguments raise ArgumentError , "Bad public_key key length" unless public_key.length.equal? 32 raise ArgumentError , "Bad signature length" unless signature.length.equal? 64 _A = point_decompress(public_key) return false if _A.nil? || _A.equal?(0) _Rs = signature[0,32] _R = point_decompress(_Rs) return false if _R.nil? || _R.equal?(0) s = int_form_bytes(signature[32,32]) return false if s >= @@q h = hash512_modq(_Rs + public_key + message) sB = point_mul(s, @@G) hA = point_mul(h, _A) return point_equal(sB, point_add(_R, hA)) end
Points are represented as array [X, Y, Z, T] of extended coordinates, with x = X/Z, y = Y/Z, x*y = T/Z
- arguments
-
pa : point A pb : point B
# File lib/ed25519_keccak/ed25519base.rb, line 132 def point_add( pa , pb ) _A = (pa[1]-pa[0]) * (pb[1]-pb[0]) % @@p _B = (pa[1]+pa[0]) * (pb[1]+pb[0]) % @@p _C = 2 * pa[3] * pb[3] * @@d % @@p _D = 2 * pa[2] * pb[2] % @@p _E = _B - _A _F = _D - _C _G = _D + _C _H = _B + _A return [ _E*_F , _G*_H , _F*_G , _E*_H ] end
compress element of ed25519 curve
Compressed format of Point(x,y) =¶ ↑
- y0,y1…y253,y254 | x0
-
ArgumentError ,
Change the most significant bit of “y” to the least significant bit of “x” The most significant bit of “y” is always zero because “0 <= y < 2^255-19”
# File lib/ed25519_keccak/ed25519base.rb, line 195 def point_compress(p) zinv = modp_inv(p[2]) x = p[0] * zinv % @@p y = p[1] * zinv % @@p # OR can be used to set the least significant bit of x to the most significant bit of y # because the most significant bit of "y" is always zero c = y | ((x & 1) << 255) return int_to_bytes(y | ((x & 1) << 255) , 32) end
decompress point that is compressed into 32bytes
# File lib/ed25519_keccak/ed25519base.rb, line 206 def point_decompress(s) # check argument raise ArgumentError , "Invalid input length for decompression" unless s.length.equal? 32 y = int_form_bytes(s) sign = y >> 255 y &= (1 << 255) - 1 x = recover_x(y, sign) if x.nil? then return nil else return [x, y, 1, x*y % @@p] end end
return point A == point B
# File lib/ed25519_keccak/ed25519base.rb, line 156 def point_equal(pa, pb) # x1 / z1 == x2 / z2 <==> x1 * z2 == x2 * z1 return false if (pa[0] * pb[2] - pb[0] * pa[2]) % @@p != 0 return false if (pa[1] * pb[2] - pb[1] * pa[2]) % @@p != 0 return true end
Computes pointQ = s * pointA
# File lib/ed25519_keccak/ed25519base.rb, line 145 def point_mul(s, pa) pq = [0, 1, 1, 0] # Neutral element while s > 0 do pq = point_add(pq, pa) unless (s & 1).equal? 0 pa = point_add(pa, pa) s >>= 1 end return pq end
calculate base**exponent % modulus
# File lib/ed25519_keccak/ed25519base.rb, line 98 def pow_mod(base, exponent, modulus) raise ArgumentError if exponent<0 || modulus<0 # result of Nmod1 is always 0 return 0 if modulus.equal? 1 result = 1 base = base % modulus while exponent > 0 result = result*base%modulus if (exponent%2).equal? 1 exponent = exponent >> 1 base = base*base%modulus end return result end
Compute corresponding x-coordinate, with low bit corresponding to sign, or return nil on failure
# File lib/ed25519_keccak/ed25519base.rb, line 168 def recover_x(y, sign) return nil if y >= @@p # x2 means x^2 x2 = (y*y-1) * modp_inv(@@d*y*y+1) # when x2==0 and sign!=0, these combination of arguments is illegal if x2.equal? 0 then unless sign.equal? 0 then return nil else return 0 end end # Compute square root of x2 x = pow_mod(x2 , ((@@p+3) / 8) , @@p) x = x * @@modp_sqrt_m1 % @@p unless ((x*x - x2) % @@p).equal? 0 return nil unless ((x*x - x2) % @@p).equal? 0 x = @@p - x unless (x & 1).equal? sign return x end
hash512(secret)
> HASH(512bit)¶ ↑
> [LH(256bit)] / [RH(256bit)]¶ ↑
> LH -> (set some bits) -> a¶ ↑
return ( a , RH )
# File lib/ed25519_keccak/ed25519base.rb, line 229 def secret_expand(secret) raise "Bad size of private key" unless secret.length.equal? 32 h = hash512(secret) a = int_form_bytes(h[0,32]) a &= (1 << 254) - 8 a |= (1 << 254) return [a, h[32,32]] end