[UIUCTF 2022] crypto ASR,WringingRing
crypto-2 ASR
基本上ASR就是RSA的代称了。
原题
from secret import flag
from Crypto.Util.number import bytes_to_long, getPrime, isPrime
from math import prod
small_primes = [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37]
def gen_prime(bits, lim = 7, sz = 64):
while True:
p = prod([getPrime(sz) for _ in range(bits//sz)])
for i in range(lim):
if isPrime(p+1):
return p+1
p *= small_primes[i]
p = gen_prime(512)
q = gen_prime(512)
n = p*q
phi = (p-1)*(q-1)
e = 0x10001
d = pow(e, -1, phi)
msg = bytes_to_long(flag)
ct = pow(msg, e, n)
print("e = ", e)
print("d = ", d)
print("ct = ", ct)
'''
e = 65537
d = 195285722677343056731308789302965842898515630705905989253864700147610471486140197351850817673117692460241696816114531352324651403853171392804745693538688912545296861525940847905313261324431856121426611991563634798757309882637947424059539232910352573618475579466190912888605860293465441434324139634261315613929473
ct = 212118183964533878687650903337696329626088379125296944148034924018434446792800531043981892206180946802424273758169180391641372690881250694674772100520951338387690486150086059888545223362117314871848416041394861399201900469160864641377209190150270559789319354306267000948644929585048244599181272990506465820030285
'''
这里只给了e,d,c没有给n也就没法直接用ed来分解n了。
不过p,q生成的方式比较特殊,先生成8个64位素数然后相乘,再乘以2,3,5,...(最多7个) 最后+1得到p,q
由于 所以有 k*phi = e*d -1 这时候对k*phi进行分解质因数可以得到
2^12 * 3^3 * 5^3 * 7^2 * 11 * ...
后边是16个64位的素数,显然将这16个素数分两组然后再乘2,3,5,7,(11)再加1就得到p,q
from Crypto.Util.number import bytes_to_long, long_to_bytes, getPrime, isPrime
e = 65537
d = 195285722677343056731308789302965842898515630705905989253864700147610471486140197351850817673117692460241696816114531352324651403853171392804745693538688912545296861525940847905313261324431856121426611991563634798757309882637947424059539232910352573618475579466190912888605860293465441434324139634261315613929473
ct = 212118183964533878687650903337696329626088379125296944148034924018434446792800531043981892206180946802424273758169180391641372690881250694674772100520951338387690486150086059888545223362117314871848416041394861399201900469160864641377209190150270559789319354306267000948644929585048244599181272990506465820030285
k_phi = e*d -1
k_phi = 12798440407105031908999784124548472446040018889572960817730530853573947469787170113848247037843114210766860084237698041237300679054325293570244618517445055261481120413825585349170515207419290554629935870091105933806157817778443160330590022707245776617234034051475753857980562266052844635281301139210583841390095872000
# 2^12 * 3^3 * 5^3 * 7^2 * 11 * ...
'''
P20 = 13923226921736843531
P20 = 15789155524315171763
P20 = 11157595634841645959
P20 = 16303174734043925501
P20 = 10476183267045952117
P20 = 10441209995968076929
P20 = 10357495682248249393
P20 = 11865228112172030291
P20 = 12775011866496218557
P20 = 16070004423296465647
P20 = 14695627525823270231
P20 = 13403263815706423849
P20 = 14497899396819662177
P20 = 18318015934220252801
P20 = 16755840154173074063
P20 = 17757525673663327889
'''
pa = [13923226921736843531,15789155524315171763,11157595634841645959,16303174734043925501,10476183267045952117,10441209995968076929,10357495682248249393,11865228112172030291,12775011866496218557,16070004423296465647,14695627525823270231,13403263815706423849,14497899396819662177,18318015934220252801,16755840154173074063,17757525673663327889]
#p,q分别为pa取8个再乘2,3,5,7,(11) +1得到
for i in [2,2,3,3,5,5,7,7,11]:
k_phi //=i
def get_pq(idx, tp,tq, np,nq):
if np==8:
if not isPrime(tp+1):
return
if nq==8:
if not isPrime(tq+1):
return
if idx >= 16:
print(tp+1, tq+1)
p = tp+1
q = tq+1
n = p*q
m = pow(ct, d, n)
print(m)
print(long_to_bytes(m))
return
if np<8:
get_pq(idx+1, tp*pa[idx], tq, np+1, nq)
if nq<8:
get_pq(idx+1, tp, tq*pa[idx], np, nq+1)
get_pq(0, 2*3*5*7, 2*3*5*7*11,0,0)
#uiuctf{bru4e_f0rc3_1s_FUn_fuN_Fun_f0r_The_whOLe_F4miLY!}
虽然有16层,但爆破题不大
crypto-3 WringingRing
这个由于没有远端只能测下程序
import sympy as sp
import random
import signal
#from secret import FLAG
FLAG = 'flag{testxxxxxx}'
secret = random.SystemRandom().randint(1, 500_000) #19位数
print("secret:", secret)
_MAX = 10 ** (len(str(secret)) - 1) # 10**5
# generating a polynomial
def _f(secret, minimum=3):
coeffs = [secret] + [
random.SystemRandom().randint(1, _MAX) for _ in range(minimum - 1)
]
# print("Secret Polynomial:")
# f_str = str(secret)
# for i, coeff in enumerate(coeffs[1:]):
# f_str += " + " + str(coeff) + "*x^" + str(i + 1)
# print(f_str)
def f(x):
res = 0
for i, coeff in enumerate(coeffs):
res += coeff * x ** (i)
return res
return f
def gen_shares(secret, minimum=3):
f = _f(secret, minimum)
shares = [(i + 1, f(i + 1)) for i in range(minimum)]
return shares
def challenge(secret, minimum=3):
shares = gen_shares(secret, minimum)
print(shares)
points = random.sample(shares, minimum - 1)
print(points)
points.sort()
return points
def main():
minimum = 10
points = challenge(secret, minimum)
print("[SSSS] Known shares of the secret polynomial: ")
for point in points:
print(f" {point}")
print()
#signal.alarm(60)
guess = int(input("[SSSS] Enter my secret: "))
if guess == secret:
print(f"[SSSS] Correct! {FLAG}")
else:
print("[SSSS] Incorrect...")
if __name__ == "__main__":
main()
'''
Wringing Rings - 139 points
"comic book style person at a chalkboard drawing a curve"
crypto
Everyone says we should use finite fields, but I loved sharing secrets this way so much that I put a ring on it!
$ nc ring.chal.uiuc.tf 1337
author: Spamakin
'''
先成生10个数,第1个是secret这个数小于500000(500_000中间的下划线是分隔符直接去掉就行),后9个比它小一位(10进制),然后这些数作10次运算生成10个数会显示出9个。
这10次运算的,虽然只给了9个但是影响不大,直接用z3
from z3 import *
from pwn import *
'''
context.log_level = 'debug'
p = remote("ring.chal.uiuc.tf", 1337)
p.recvuntil(b'[SSSS] Known shares of the secret polynomial:\n')
points = []
for i in range(9):
p.append(eval(p.recvline()))
print(points)
'''
data = '''
(1, 104137)
(3, 73506441)
(4, 879095644)
(5, 6249646673)
(6, 31430072352)
(7, 123848462689)
(8, 407425874756)
(9, 1166688459129)
(10, 2993217169048)
'''
data = data.strip().split("\n")
points = []
for v in data:
points.append(eval(v))
print(points)
c = [Int(f'c{i}') for i in range(10)]
s = Solver()
s.add(c[0]>0)
s.add(c[0]<500000)
for i in range(1,10):
s.add(c[i]>0)
s.add(c[i]<100000)
for (i,n) in points:
r = 0
for j in range(10):
r += c[j]*i**j
s.add(r == n)
s.check()
d = s.model()
d = d[c[0]].as_long()
print(d)
#p.sendline(str(d).encode())