Module: Laicrypto

Defined in:
lib/laicrypto.rb,
lib/laicrypto/version.rb

Defined Under Namespace

Classes: Error

Constant Summary collapse

VERSION = 
"0.1.0"

Class Method Summary collapse

Class Method Details

._pow_T_range(P, start_s, exp, a, p) ⇒ Object

_pow_T_range(P, start_s, exp, a, p): apply T iteratively exp times, starting seed = start_s



109
110
111
112
113
114
115
116
117
 
# File 'lib/laicrypto.rb', line 109

def self._pow_T_range(P, start_s, exp, a, p)
  result = P.dup
  curr_s = start_s
  exp.times do
    result = T(result, curr_s, a, p)
    curr_s += 1
  end
  result
end

.decrypt(C1, C2, k, r, a, p) ⇒ Object

decrypt(C1, C2, k, r, a, p) → Integer (original message)



158
159
160
161
162
 
# File 'lib/laicrypto.rb', line 158

def self.decrypt(C1, C2, k, r, a, p)
  S  = _pow_T_range(C1, r + 1, k, a, p)
  M0 = (C2[0] - S[0]) % p
  M0 < 0 ? M0 + p : M0
end

.encrypt(m, public_Q, k, p, a, P0) ⇒ Object

encrypt(m, public_Q, k, p, a, P0) → { C1: [x,y], C2: [x,y], r: Integer }



133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
 
# File 'lib/laicrypto.rb', line 133

def self.encrypt(m, public_Q, k, p, a, P0)
  loop do
    r = rand(1...p)
    # Compute C1 = T^r(P0) with seeds 1..r
    begin
      C1 = _pow_T_range(P0, 1, r, a, p)
    rescue Error
      next
    end

    # Compute Sr = T^r(public_Q) with seeds (k+1)..(k+r)
    begin
      Sr = _pow_T_range(public_Q, k + 1, r, a, p)
    rescue Error
      next
    end

    M0 = m % p
    M  = [ M0 < 0 ? M0 + p : M0, 0 ]
    C2 = [ (M[0] + Sr[0]) % p, (M[1] + Sr[1]) % p ]
    return { C1: C1, C2: C2, r: r }
  end
end

.H(x, y, s, p) ⇒ Object

H(x, y, s, p) = SHA256(x || y || s) mod p



8
9
10
11
12
13
 
# File 'lib/laicrypto.rb', line 8

def self.H(x, y, s, p)
  data      = "#{x}|#{y}|#{s}"
  digest    = Digest::SHA256.digest(data)
  digest_bn = digest.unpack1("H*").to_i(16)
  digest_bn % p
end

.keygen(p, a, P0) ⇒ Object

keygen(p, a, P0) → { k: Integer, Q: [x,y] }



120
121
122
123
124
125
126
127
128
129
130
 
# File 'lib/laicrypto.rb', line 120

def self.keygen(p, a, P0)
  loop do
    k_candidate = rand(1...p)
    begin
      Q = _pow_T_range(P0, 1, k_candidate, a, p)
      return { k: k_candidate, Q: Q }
    rescue Error
      next
    end
  end
end

.mod_pow(base, exp, mod) ⇒ Object

mod_pow(base, exp, mod): base^exp mod mod (exponentiation by squaring)



16
17
18
19
20
21
22
23
24
25
26
27
28
 
# File 'lib/laicrypto.rb', line 16

def self.mod_pow(base, exp, mod)
  result = 1
  b      = base % mod
  e      = exp

  while e > 0
    result = (result * b) % mod if (e & 1) != 0
    b = (b * b) % mod
    e >>= 1
  end

  result
end

.sqrt_mod(a, p) ⇒ Object

sqrt_mod(a, p): Tonelli–Shanks to find sqrt modulo p (p prime). Return nil if no root.



31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
 
# File 'lib/laicrypto.rb', line 31

def self.sqrt_mod(a, p)
  a = a % p
  return 0 if a == 0

  # Legendre symbol: a^((p-1)//2) mod p
  ls = mod_pow(a, (p - 1) / 2, p)
  return nil if ls == p - 1

  # Shortcut if p % 4 == 3
  if p % 4 == 3
    return mod_pow(a, (p + 1) / 4, p)
  end

  # Tonelli–Shanks for p ≡ 1 (mod 4)
  q = p - 1
  s = 0
  while (q & 1) == 0
    q >>= 1
    s += 1
  end

  # Find z: a quadratic non-residue
  z = 2
  while mod_pow(z, (p - 1) / 2, p) != p - 1
    z += 1
  end

  m = s
  c = mod_pow(z, q, p)
  t = mod_pow(a, q, p)
  r = mod_pow(a, (q + 1) / 2, p)

  loop do
    return r if t == 1
    # Find smallest i: t^(2^i) ≡ 1 (mod p)
    t2i = t
    i   = 0
    (1...m).each do |j|
      t2i = (t2i * t2i) % p
      if t2i == 1
        i = j
        break
      end
    end
    # Compute next values
    b = mod_pow(c, 1 << (m - i - 1), p)
    m = i
    c = (b * b) % p
    t = (t * c) % p
    r = (r * b) % p
  end
end

.T(point, s, a, p) ⇒ Object

T(point, s, a, p): transformation

x' = (x + a + H(x,y,s)) * inv2 mod p
y' = sqrt_mod(x*y + H(x,y,s), p)

If sqrt_mod returns nil, increment s (up to 10 tries)

Raises:



88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
 
# File 'lib/laicrypto.rb', line 88

def self.T(point, s, a, p)
  x, y   = point
  inv2   = mod_pow(2, p - 2, p)  # modular inverse of 2 mod p
  trials = 0
  s_current = s

  while trials < 10
    h = H(x, y, s_current, p)
    x_candidate = ((x + a + h) * inv2) % p
    y_sq = (x * y + h) % p
    y_candidate = sqrt_mod(y_sq, p)
    return [x_candidate, y_candidate] unless y_candidate.nil?

    s_current += 1
    trials += 1
  end

  raise Error, "T: Gagal menemukan sqrt untuk y^2=#{y_sq} mod #{p} setelah #{trials} percobaan."
end