EzRSA

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
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
import sys

import random

from sympy import nextprime

import binascii

FLAG = b"flag{xxxxxxx}"

BIT_SIZE = 512

DIFF = 1000

def generate_close_primes(bit_size, diff):

  start = random.getrandbits(bit_size) | 1

  p = nextprime(start)

  q = nextprime(p + diff)

  return p, q

def flag_to_int(flag_bytes):

  return int.from_bytes(flag_bytes, byteorder='big')

def main():

  p, q = generate_close_primes(BIT_SIZE, DIFF)

  n = p * q

  e = 3

  m = flag_to_int(FLAG)

  c = pow(m, e, n)

  print(f"n = {n}")

  print(f"e = {e}")

  print(f"c = {c}")

if __name__ == "__main__":

  main()

"""

n = 3256593900815599638610948588846270419272266309072355018531019815816383416972716648196614202756266923662468043040766972587895880348728177684427108179441398076920699534139836200520410133083399544975367893285080239622582380507397956076038256757810824984700446326253944197017126171652309637891515864542581815539

e = 3

c = 1668144786169714702301094076704686642891065952249900945234348491495868262367689770718451252978033214169821458376529832891775500377565608075759008139982766645172498702491199793075638838575243018129218596030822468832530007275522627172632933

"""

先说一个非预期的解法吧

因为这里的e=3,所以我们可以直接对m开三次方这样可以得到flag

1
2
3
4
5
6
7
8
from gmpy2 import iroot
from Crypto.Util.number import *
c = 1668144786169714702301094076704686642891065952249900945234348491495868262367689770718451252978033214169821458376529832891775500377565608075759008139982766645172498702491199793075638838575243018129218596030822468832530007275522627172632933
m = iroot(c, 3)[0]
flag = int(m).to_bytes((int(m).bit_length() + 7) // 8, 'big')
print(flag)
#print(long_to_bytes(m))  直接用这个也行

再说说预期的解法

1
2
3
4
5
6
7
8
9
def generate_close_primes(bit_size, diff):

  start = random.getrandbits(bit_size) | 1

  p = nextprime(start)

  q = nextprime(p + diff)

  return p, q

这里就是生成两个相邻素数p,q

其中q是p + DIFF的下一个素数

我们可以用费马分解求出p,q

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
from math import isqrt

import gmpy2

from Crypto.Util.number import *

def fermat(n):

  a = isqrt(n)

  b2 = a * a - n

  b = isqrt(n)

  count = 0

  while b * b != b2:

    a = a + 1

    b2 = a * a - n

    b = isqrt(b2)

    count += 1

  p = a + b

  q = a - b

  assert n == p * q

  return p, q

if __name__ == '__main__':

  n = 3256593900815599638610948588846270419272266309072355018531019815816383416972716648196614202756266923662468043040766972587895880348728177684427108179441398076920699534139836200520410133083399544975367893285080239622582380507397956076038256757810824984700446326253944197017126171652309637891515864542581815539

  e = 3

  c = 1668144786169714702301094076704686642891065952249900945234348491495868262367689770718451252978033214169821458376529832891775500377565608075759008139982766645172498702491199793075638838575243018129218596030822468832530007275522627172632933

  p, q = fermat(n)

  print("p=", p)

  print("q=", q)


这里我们发现e与phi不互素

1
GCD(e, phi) = 3

因为这里很小，我们可以用公约数暂约来做

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
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
from math import isqrt

import gmpy2

from Crypto.Util.number import *

def fermat(n):

  a = isqrt(n)

  b2 = a * a - n

  b = isqrt(n)

  count = 0

  while b * b != b2:

​    a = a + 1

​    b2 = a * a - n

​    b = isqrt(b2)

​    count += 1

  p = a + b

  q = a - b

  assert n == p * q

  return p, q

if __name__ == '__main__':

  n = 3256593900815599638610948588846270419272266309072355018531019815816383416972716648196614202756266923662468043040766972587895880348728177684427108179441398076920699534139836200520410133083399544975367893285080239622582380507397956076038256757810824984700446326253944197017126171652309637891515864542581815539

  e = 3

  c = 1668144786169714702301094076704686642891065952249900945234348491495868262367689770718451252978033214169821458376529832891775500377565608075759008139982766645172498702491199793075638838575243018129218596030822468832530007275522627172632933

  p, q = fermat(n)

  print("p=", p)

  print("q=", q)

  phi = (p - 1) * (q - 1)

  t = gmpy2.gcd(e,phi)

if t != 1:

 print(t)

 e1 = e // t

 d = gmpy2.invert(e1,phi)

 m = pow(c,d,n)

 print(long_to_bytes(gmpy2.iroot(m,t)[0]))

Quaternion Lock

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
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
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
import random

p = 9223372036854775783 

e = 65537

subgroup_order = 60480

def qmul(q1, q2, p):

  a1, b1, c1, d1 = q1

  a2, b2, c2, d2 = q2

  return (

​    (a1*a2 - b1*b2 - c1*c2 - d1*d2) % p,

​    (a1*b2 + b1*a2 + c1*d2 - d1*c2) % p,

​    (a1*c2 - b1*d2 + c1*a2 + d1*b2) % p,

​    (a1*d2 + b1*c2 - c1*b2 + d1*a2) % p

  )

def qconj(q, p):

  a, b, c, d = q

  return (a % p, (-b) % p, (-c) % p, (-d) % p)

def qnorm(q, p):

  a, b, c, d = q

  return (a*a + b*b + c*c + d*d) % p

def qinv(q, p):

  n = qnorm(q, p)

  inv_n = pow(n, -1, p)

  qc = qconj(q, p)

  return (qc[0] * inv_n % p, qc[1] * inv_n % p, qc[2] * inv_n % p, qc[3] * inv_n % p)

def qpow(q, exp, p):

  result = (1, 0, 0, 0)

  base = q

  while exp:

​    if exp & 1:

​      result = qmul(result, base, p)

​    base = qmul(base, base, p)

​    exp //= 2

  return result

def encode_flag(flag):

  flag_bytes = flag.encode()

  parts = [flag_bytes[0:8], flag_bytes[8:15], flag_bytes[15:22], flag_bytes[22:29]]

  return tuple(int.from_bytes(part, 'big') for part in parts)

def main():

  flag = "flag{xxx-xxx-xxx-xxx-xxx-xxx}"

  F = encode_flag(flag)

  F_q = F

  g = (2, 1, 0, 0)

  h = qpow(g, ((p * p - 1) // subgroup_order), p)

  r = random.randint(1, subgroup_order - 1)

  K = qpow(h, r, p)

  Y = qpow(K, e, p)

  K_inv = qinv(K, p)

  X = qmul(K, qmul(F_q, K_inv, p), p)

  print("----- Public Parameters -----")

  print("p =", p)

  print("e =", e)

  print("X =", X) 

  print("Y =", Y) 

  print("-----------------------------")

if __name__ == "__main__":

  main()

'''

X = (7380380986429696832, 34163292457091182, 3636630423226195928, 3896730209645707435)

Y = (1015918725738180802, 4456058114364993854, 0, 0)

'''

这里一个基于四元数的加密系统,这篇文章有介绍

  • qmul(q1, q2, p): 四元数乘法（模 p）
    • 计算两个四元数 q1 和 q2 的乘积，并对每个分量取模 p。
  • qconj(q, p): 四元数共轭
    • 返回四元数 q 的共轭（即 (a, -b, -c, -d)）。
  • qnorm(q, p): 四元数范数（模长的平方）
    • 计算 a² + b² + c² + d² mod p。
  • qinv(q, p): 四元数逆元
    • 通过共轭和范数的逆元计算四元数的乘法逆元。
  • qpow(q, exp, p): 四元数的快速幂
    • 使用快速幂算法计算四元数 q 的 exp 次幂

这里flag被分为四个部分，然后转为整数

1
2
3
4
5
6
7
def encode_flag(flag):

  flag_bytes = flag.encode()

  parts = [flag_bytes[0:8], flag_bytes[8:15], flag_bytes[15:22], flag_bytes[22:29]]

  return tuple(int.from_bytes(part, 'big') for part in parts)

同时给了三个参数

1
2
3
4
5
6
7
p = 9223372036854775783 

e = 65537

subgroup_order = 60480   #子群的阶

g = (2, 1, 0, 0)         #一个固定的四元数，作为生成元

生成密钥

1
2
3
4
5
6
7
h = qpow(g, ((p * p - 1) // subgroup_order), p)

r = random.randint(1, subgroup_order - 1)

K = qpow(h, r, p)

Y = qpow(K, e, p)

加密等式

1
2
3
K_inv = qinv(K, p)

X = qmul(K, qmul(F_q, K_inv, p), p)

现在需要先恢复K

我们直接枚举爆破出K，然后算出K_inv

最后F_q = K_inv * X * K mod p

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
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
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
def qmul(q1, q2, p):

  a1, b1, c1, d1 = q1

  a2, b2, c2, d2 = q2

  return (

​    (a1*a2 - b1*b2 - c1*c2 - d1*d2) % p,

​    (a1*b2 + b1*a2 + c1*d2 - d1*c2) % p,

​    (a1*c2 - b1*d2 + c1*a2 + d1*b2) % p,

​    (a1*d2 + b1*c2 - c1*b2 + d1*a2) % p

  )

def qconj(q, p):

  a, b, c, d = q

  return (a % p, (-b) % p, (-c) % p, (-d) % p)

def qnorm(q, p):

  a, b, c, d = q

  return (a*a + b*b + c*c + d*d) % p

def qinv(q, p):

  n = qnorm(q, p)

  inv_n = pow(n, -1, p)

  qc = qconj(q, p)

  return (qc[0] * inv_n % p, qc[1] * inv_n % p, qc[2] * inv_n % p, qc[3] * inv_n % p)

def qpow(q, exp, p):

  result = (1, 0, 0, 0)

  base = q

  while exp:

​    if exp & 1:

​      result = qmul(result, base, p)

​    base = qmul(base, base, p)

​    exp //= 2

  return result

def decrypt(p, e, subgroup_order, X, Y):

  g = (2,1,0,0)

  h = qpow(g, ((p*p - 1)//subgroup_order), p)

  \# brute force for K

  for r in range(1, subgroup_order):

​    Kcand = qpow(h, r, p)

​    if qpow(Kcand, e, p) == Y:

​      K = Kcand

​      break

  else:

​    raise Exception("K not found!")

  

  \# F = K^-1 * X * K

  K_inv = qinv(K, p)

  F_q = qmul(K_inv, qmul(X, K, p), p)

  return F_q

\# 测试数据

p = 9223372036854775783 

e = 65537

subgroup_order = 60480

X = (7380380986429696832, 34163292457091182, 3636630423226195928, 3896730209645707435)

Y = (1015918725738180802, 4456058114364993854, 0, 0)

F_q = decrypt(p, e, subgroup_order, X, Y)

print("Recovered quaternion:", F_q)

print("Recovered flag:", b"".join(x.to_bytes((x.bit_length()+7)//8, 'big') for x in F_q))