Module: Nem::Util::Ed25519

Defined in:
lib/nem/util/ed25519.rb

Defined Under Namespace

Classes: SignatureMismatch

Constant Summary collapse

@@b = 
256
@@q = 
2**255 - 19
@@l = 
2**252 + 27742317777372353535851937790883648493
@@d = 
-121665 * self.inv(121666) % @@q
@@I = 
2.to_bn.mod_exp((@@q - 1) / 4, @@q)
@@By = 
4 * self.inv(5)
@@Bx = 
self.xrecover(@@By)
@@B = 
[@@Bx % @@q, @@By % @@q, 1, (@@Bx * @@By) % @@q]
@@ident = 
[0, 1, 1, 0]
@@Bpow = 
[]

Class Method Summary collapse

Class Method Details

.bit(h, i) ⇒ Object 



148
149
150
 
# File 'lib/nem/util/ed25519.rb', line 148

def bit(h, i)
  (indexbytes(h, i / 8) >> (i % 8)) & 1
end

.checkvalid(s, m, pk) ⇒ Object

Not safe to use when any argument is secret. This function should be used only for verifying public signatures of public messages.



282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
 
# File 'lib/nem/util/ed25519.rb', line 282

def checkvalid(s, m, pk)
  raise 'signature length is wrong' if s.size != @@b / 4
  raise 'public-key length is wrong' if pk.size != @@b / 8

  _R = decodepoint(s[0...@@b / 8])
  _A = decodepoint(pk)
  _S = decodeint(s[@@b / 8...@@b / 4])
  h = Hint(encodepoint(_R) + pk + m)

  x1, y1, z1, _t1 = _P = scalarmult_B(_S)
  x2, y2, z2, _t2 = _Q = edwards_add(_R, scalarmult(_A, h))

  if (!isoncurve(_P) || !isoncurve(_Q) || (x1 * z2 - x2 * z1) % q != 0 || (y1 * z2 - y2 * z1) % q != 0)
    raise SignatureMismatch('signature does not pass verification')
  end
end

.decodeint(s) ⇒ Object 



263
264
265
 
# File 'lib/nem/util/ed25519.rb', line 263

def decodeint(s)
  (0...@@b).inject(0) { |sum, i| sum + 2**i * bit(s, i) }
end

.decodepoint(s) ⇒ Object 



267
268
269
270
271
272
273
274
 
# File 'lib/nem/util/ed25519.rb', line 267

def decodepoint(s)
  y = (0...@@b - 1).inject(0) { |sum, i| sum + 2**i * bit(s, i) }
  x = xrecover(y)
  x = @@q - x if x & 1 != bit(s, @@b - 1)
  _P = [x, y, 1, (x * y) % @@q]
  raise 'decoding point that is not on curve' unless isoncurve(_P)
  _P
end

.decrypt(sk, pk, data) ⇒ Object 



193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
 
# File 'lib/nem/util/ed25519.rb', line 193

def decrypt(sk, pk, data)
  h = HH(sk)
  a = 2**(@@b - 2) + (3...@@b - 2).inject(0) { |sum, i| sum + 2**i * bit(h, i) }
  _A = decodepoint(pk)
  bin_g = encodepoint(scalarmult(_A, a))

  hex_salt = data[0, 64]
  hex_iv = data[64, 32]
  hex_encrypted = data[96, data.size]

  ua_iv = Nem::Util::Convert.hex2ua(hex_iv)
  bin_iv = ua_iv.pack('C*')

  ua_salt = Nem::Util::Convert.hex2ua(hex_salt)
  ua_g = Nem::Util::Convert.hex2ua(bin_g.unpack('H*').first)

  c = []
  ua_salt.each_with_index { |el, idx| c << (el ^ ua_g[idx]) }
  bin_key = Digest::SHA3.digest(c.pack('C*'), 256)

  bin_encrypted = Nem::Util::Convert.hex2ua(hex_encrypted).pack('C*')

  cipher = OpenSSL::Cipher.new('AES-256-CBC')
  cipher.decrypt
  cipher.key = bin_key
  cipher.iv = bin_iv
  cipher.update(bin_encrypted) + cipher.final
end

.edwards_add(_P, _Q) ⇒ Object 



63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
 
# File 'lib/nem/util/ed25519.rb', line 63

def edwards_add(_P, _Q)
  # This is formula sequence 'addition-add-2008-hwcd-3' from
  # http://www.hyperelliptic.org/EFD/g1p/auto-twisted-extended-1.html
  x1, y1, z1, t1 = _P
  x2, y2, z2, t2 = _Q

  a = (y1 - x1) * (y2 - x2) % @@q
  b = (y1 + x1) * (y2 + x2) % @@q
  c = t1 * 2 * @@d * t2 % @@q
  dd = z1 * 2 * z2 % @@q
  e = b - a
  f = dd - c
  g = dd + c
  h = b + a
  x3 = e * f
  y3 = g * h
  t3 = e * h
  z3 = f * g

  [x3 % @@q, y3 % @@q, z3 % @@q, t3 % @@q]
end

.edwards_double(_P) ⇒ Object 



85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
 
# File 'lib/nem/util/ed25519.rb', line 85

def edwards_double(_P)
  # This is formula sequence 'dbl-2008-hwcd' from
  # http://www.hyperelliptic.org/EFD/g1p/auto-twisted-extended-1.html
  x1, y1, z1, _t1 = _P

  a = x1 * x1 % @@q
  b = y1 * y1 % @@q
  c = 2 * z1 * z1 % @@q
  # dd = -a
  e = ((x1 + y1) * (x1 + y1) - a - b) % @@q
  g = -a + b  # dd + b
  f = g - c
  h = -a - b  # dd - b
  x3 = e * f
  y3 = g * h
  t3 = e * h
  z3 = f * g

  [x3 % @@q, y3 % @@q, z3 % @@q, t3 % @@q]
end

.encodeint(y) ⇒ Object 



134
135
136
137
 
# File 'lib/nem/util/ed25519.rb', line 134

def encodeint(y)
  bits = (0...@@b).map { |i| (y >> i) & 1 }
  (0...@@b / 8).inject('') { |memo, i| memo << int2byte((0...8).inject(0) { |sum, j| sum + (bits[i * 8 + j] << j) }) }
end

.encodepoint(_P) ⇒ Object 



139
140
141
142
143
144
145
146
 
# File 'lib/nem/util/ed25519.rb', line 139

def encodepoint(_P)
  x, y, z, _t = _P
  zi = inv(z)
  x = (x * zi) % @@q
  y = (y * zi) % @@q
  bits = (0...@@b - 1).map { |i| (y >> i) & 1 } + [x & 1]
  (0...@@b / 8).inject('') { |memo, i| memo << int2byte((0...8).inject(0) { |sum, j| sum + (bits[i * 8 + j] << j) }) }
end

.encrypt(sk, pk, data) ⇒ Object 



166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
 
# File 'lib/nem/util/ed25519.rb', line 166

def encrypt(sk, pk, data)
  h = HH(sk)
  a = 2**(@@b - 2) + (3...@@b - 2).inject(0) { |sum, i| sum + 2**i * bit(h, i) }
  _A = decodepoint(pk)
  bin_g = encodepoint(scalarmult(_A, a))

  bin_iv = SecureRandom.random_bytes(16)
  hex_iv = bin_iv.unpack('H*').first

  bin_salt = SecureRandom.random_bytes(32)
  hex_salt = bin_salt.unpack('H*').first

  ua_salt = Nem::Util::Convert.hex2ua(hex_salt)
  ua_g = Nem::Util::Convert.hex2ua(bin_g.unpack('H*').first)

  c = []
  ua_salt.each_with_index { |el, idx| c << (el ^ ua_g[idx]) }
  bin_key = Digest::SHA3.digest(c.pack('C*'), 256)

  cipher = OpenSSL::Cipher.new('AES-256-CBC')
  cipher.encrypt
  cipher.key = bin_key
  cipher.iv = bin_iv
  encrypted_data = cipher.update(data.bytes.pack('C*')) + cipher.final
  hex_salt + hex_iv + encrypted_data.unpack('H*').first
end

.H(m) ⇒ Object

standard implement



23
24
25
 
# File 'lib/nem/util/ed25519.rb', line 23

def H(m)
  OpenSSL::Digest::SHA512.digest(m)
end

.HH(m) ⇒ Object 



27
28
29
 
# File 'lib/nem/util/ed25519.rb', line 27

def HH(m)
  Digest::SHA3.digest(m)
end

.Hint(m) ⇒ Object 



222
223
224
225
 
# File 'lib/nem/util/ed25519.rb', line 222

def Hint(m)
  h = H(m)
  (0...2 * @@b).inject(0) { |sum, i| sum + 2**i * bit(h, i) }
end

.Hint_hash(m) ⇒ Object 



227
228
229
230
 
# File 'lib/nem/util/ed25519.rb', line 227

def Hint_hash(m)
  h = HH(m)
  (0...2 * @@b).inject(0) { |sum, i| sum + 2**i * bit(h, i) }
end

.indexbytes(buf, i) ⇒ Object 



14
15
16
 
# File 'lib/nem/util/ed25519.rb', line 14

def indexbytes(buf, i)
  buf[i].ord
end

.int2byte(i) ⇒ Object 



10
11
12
 
# File 'lib/nem/util/ed25519.rb', line 10

def int2byte(i)
  i.chr
end

.intlist2bytes(l) ⇒ Object 



18
19
20
 
# File 'lib/nem/util/ed25519.rb', line 18

def intlist2bytes(l)
  l.inject('') { |memo, c| memo << c.chr }
end

.inv(z) ⇒ Object 



39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
 
# File 'lib/nem/util/ed25519.rb', line 39

def inv(z)
  # Adapted from curve25519_athlon.c in djb's Curve25519.
  z2 = z * z % @@q  # 2
  z9 = pow2(z2, 2) * z % @@q  # 9
  z11 = z9 * z2 % @@q  # 11
  z2_5_0 = (z11 * z11) % @@q * z9 % @@q  # 31 == 2^5 - 2^0
  z2_10_0 = pow2(z2_5_0, 5) * z2_5_0 % @@q  # 2^10 - 2^0
  z2_20_0 = pow2(z2_10_0, 10) * z2_10_0 % @@q  # ...
  z2_40_0 = pow2(z2_20_0, 20) * z2_20_0 % @@q
  z2_50_0 = pow2(z2_40_0, 10) * z2_10_0 % @@q
  z2_100_0 = pow2(z2_50_0, 50) * z2_50_0 % @@q
  z2_200_0 = pow2(z2_100_0, 100) * z2_100_0 % @@q
  z2_250_0 = pow2(z2_200_0, 50) * z2_50_0 % @@q  # 2^250 - 2^0
  pow2(z2_250_0, 5) * z11 % @@q  # 2^255 - 2^5 + 11 = q - 2
end

.isoncurve(_P) ⇒ Object 



256
257
258
259
260
261
 
# File 'lib/nem/util/ed25519.rb', line 256

def isoncurve(_P)
  x, y, z, t = _P
  (z % @@q != (0) &&
    x * y % @@q == (z * t % @@q) &&
    (y * y - x * x - z * z - @@d * t * t) % @@q == (0))
end

.make_Bpow ⇒ Object 



114
115
116
117
118
119
120
 
# File 'lib/nem/util/ed25519.rb', line 114

def make_Bpow
  _P = @@B
  253.times do
    @@Bpow << _P
    _P = edwards_double(_P)
  end
end

.pow2(x, p) ⇒ Object 



31
32
33
34
35
36
37
 
# File 'lib/nem/util/ed25519.rb', line 31

def pow2(x, p)
  while p > 0 do
    x = x.to_bn.mod_exp(2, @@q).to_i
    p -= 1
  end
  x
end

.publickey_hash_unsafe(sk) ⇒ Object 



159
160
161
162
163
164
 
# File 'lib/nem/util/ed25519.rb', line 159

def publickey_hash_unsafe(sk)
  h = HH(sk)
  a = 2**(@@b - 2) + (3...@@b - 2).inject(0) { |sum, i| sum + 2**i * bit(h, i) }
  _A = scalarmult_B(a)
  encodepoint(_A)
end

.publickey_unsafe(sk) ⇒ Object 



152
153
154
155
156
157
 
# File 'lib/nem/util/ed25519.rb', line 152

def publickey_unsafe(sk)
  h = H(sk)
  a = 2**(@@b - 2) + (3...@@b - 2).inject(0) { |sum, i| sum + 2**i * bit(h, i) }
  _A = scalarmult_B(a)
  codepoint(_A)
end

.scalarmult(_P, e) ⇒ Object 



106
107
108
109
110
111
112
 
# File 'lib/nem/util/ed25519.rb', line 106

def scalarmult(_P, e)
  return @@ident if e == 0
  _Q = scalarmult(_P, e / 2)
  _Q = edwards_double(_Q)
  _Q = edwards_add(_Q, _P) if (e & 1) == 1
  _Q
end

.scalarmult_B(e) ⇒ Object

Implements scalarmult(B, e) more efficiently.



123
124
125
126
127
128
129
130
131
132
 
# File 'lib/nem/util/ed25519.rb', line 123

def scalarmult_B(e)
  # scalarmult(B, l) is the identity
  e = e % @@l
  _P = @@ident
  253.times do |i|
    _P = edwards_add(_P, @@Bpow[i]) if e & 1 == 1
    e = e / 2
  end
  _P
end

.signature_hash_unsafe(m, sk, pk) ⇒ Object

Not safe to use with secret keys or secret data. This function should be used for testing only.



245
246
247
248
249
250
251
252
253
254
 
# File 'lib/nem/util/ed25519.rb', line 245

def signature_hash_unsafe(m, sk, pk)
  h = HH(sk)
  a = 2**(@@b - 2) + (3...@@b - 2).inject(0) { |sum, i| sum + 2**i * bit(h, i) }
  r = Hint_hash(
    intlist2bytes((@@b / 8...@@b / 4).map { |j| indexbytes(h, j) }) + m
  )
  _R = scalarmult_B(r)
  _S = (r + Hint_hash(encodepoint(_R) + pk + m) * a) % @@l
  encodepoint(_R) + encodeint(_S)
end

.signature_unsafe(m, sk, pk) ⇒ Object 



232
233
234
235
236
237
238
239
240
241
 
# File 'lib/nem/util/ed25519.rb', line 232

def signature_unsafe(m, sk, pk)
  h = H(sk)
  a = 2**(@@b - 2) + (3...@@b - 2).inject(0) { |sum, i| sum + 2**i * bit(h, i) }
  r = Hint(
    intlist2bytes((@@b / 8...@@b / 4).map { |j| indexbytes(h, j) }) + m
  )
  _R = scalarmult_B(r)
  _S = (r + Hint(encodepoint(_R) + pk + m) * a) % @@l
  encodepoint(_R) + encodeint(_S)
end

.xrecover(y) ⇒ Object 



55
56
57
58
59
60
61
 
# File 'lib/nem/util/ed25519.rb', line 55

def xrecover(y)
  xx = (y * y - 1) * inv(@@d * y * y + 1)
  x = xx.to_bn.mod_exp((@@q + 3) / 8, @@q).to_i
  x = (x * @@I) % @@q if (x * x - xx) % @@q != 0
  x = @@q - x if x % 2 != 0
  x
end