Crypto复现1 | Arashimuのblog = CTFer

# ACTF :Impossible rsa

# 知识点

代换得到二次方程的思想

# Problem

	from Crypto.Util.number import *
	from Crypto.PublicKey import RSA

	e = 65537
	flag = b'ACTF{...}'

	while True:
	p = getPrime(1024)
	q = inverse(e, p)
	if not isPrime(q):
	continue
	n = p * q;
	public = RSA.construct((n, e))
	with open("public.pem", "wb") as file:
	file.write(public.exportKey('PEM'))
	with open("flag", "wb") as file:
	file.write(long_to_bytes(pow(bytes_to_long(flag), e, n)))
	break

# Solve

已知情报：

密文 $c$
公钥 $(n,e)$
$n=pq$
eq\equiv 1\mod
c\equiv m^e\mod
要计算 $m$

推导

$eq=kp+1,n=pq\\ ne=eqp=(kp+1)p=kp^2+p\\ p^2k+p-ne=0$

得到一个一元二次方程，求根得到

$p=\frac{-1+\sqrt{1+4nek}}{2k}$

然后我们枚举 $k$ ，得到 $p$ ，判断 $p$ 是否是素数，然后得到 $q=\frac{n}{p}$ ，判断 $pq$ 是否等于 $n$ ，然后就可以根据 RSA 的正常步骤求得 $m$

	import gmpy2
	from Crypto.Util.number import *
	from Crypto.PublicKey import RSA

	e=65537
	with open("public.pem","rb") as f:
	rsa=RSA.import_key(f.read()) #利用 RSA 模块的 import_key 可以直接将.pem 文件里面的数据还原成密钥对
	n=rsa.n
	with open("flag","rb") as f:
	c=bytes_to_long(f.read())

	ne=e*n
	k=1

	while(True):
	x=4kne+1
	y,ok=gmpy2.iroot(x,2)
	if ok == True:
	p=(y-1)//k//2
	if gmpy2.is_prime(p)==True:
	break
	k+=1
	q=n//p
	d=inverse(e,(p-1)*(q-1))
	m=pow(c,d,n)
	print(long_to_bytes(m))
	# ACTF{F1nD1nG_5pEcia1_n_i5_nOt_eA5y}

# ACTF:leak_rsa

# 知识点

中间相遇攻击
代换得到一元二次方程

# Problem

	from sage.all import *
	from secret import flag
	from Crypto.Util.number import bytes_to_long


	def leak(a, b):
	p = random_prime(pow(2, 64))
	q = random_prime(pow(2, 64))
	n = p*q
	e = 65537
	print(n)
	print((pow(a, e) + pow(b, e) + 0xdeadbeef) % n)


	def gen_key():
	a = randrange(0, pow(2,256))
	b = randrange(0, pow(2,256))
	p = pow(a, 4)
	q = pow(b, 4)
	rp = randrange(0, pow(2,24))
	rq = randrange(0, pow(2,24))
	pp = next_prime(p+rp)
	qq = next_prime(q+rq)
	if pp % pow(2, 4) == (pp-p) % pow(2, 4) and qq % pow(2, 4) == (qq-q) % pow(2, 4):
	n = pp*qq
	rp = pp-p
	rq = qq-q
	return n, rp, rq

	n, rp, rq = gen_key()
	e = 65537
	c = pow(bytes_to_long(flag), e, n)
	print("n =", n)
	print("e =", e)
	print("c =", c)
	print("=======leak=======")
	leak(rp, rq)

	'''
	n = 3183573836769699313763043722513486503160533089470716348487649113450828830224151824106050562868640291712433283679799855890306945562430572137128269318944453041825476154913676849658599642113896525291798525533722805116041675462675732995881671359593602584751304602244415149859346875340361740775463623467503186824385780851920136368593725535779854726168687179051303851797111239451264183276544616736820298054063232641359775128753071340474714720534858295660426278356630743758247422916519687362426114443660989774519751234591819547129288719863041972824405872212208118093577184659446552017086531002340663509215501866212294702743
	e = 65537
	c = 48433948078708266558408900822131846839473472350405274958254566291017137879542806238459456400958349315245447486509633749276746053786868315163583443030289607980449076267295483248068122553237802668045588106193692102901936355277693449867608379899254200590252441986645643511838233803828204450622023993363140246583650322952060860867801081687288233255776380790653361695125971596448862744165007007840033270102756536056501059098523990991260352123691349393725158028931174218091973919457078350257978338294099849690514328273829474324145569140386584429042884336459789499705672633475010234403132893629856284982320249119974872840
	=======leak=======
	122146249659110799196678177080657779971
	90846368443479079691227824315092288065
	'''

已知情报：

$n,e,c$
n^{'}=p^{'}q^
(rp^{e}+rq^{e}+\text{0xdeadbeef})\%n^

可以得到的等式

$a,b\in[0,2^{256})$
$p=a^4,q=b^4$
$rp^{'},rq^{'}\in[0,2^{24})$
$pp\gt p+rp^{'}$ 并且 $pp$ 是素数
$qq\gt q+rq^{'}$ 并且 $qq$ 是素数
pp\equiv pp-p\mod
qq\equiv qq-q\mod
$n=pp\times qq$
$rp=pp-p=rp^{'}+k_1,rq=qq-q=rq^{'}+k_2$

一个很自然的想法就是先得出 $rp$ 和 $rq$ ，因为 leak 中的值基本上给出了，可以发现 $rp,rq\in[0,2^{24})$ ，因为 $k_1,k_2$ 不会太大

利用中途相遇攻击，就是先枚举所有 $rp$ ，然后根据 $rp$ 求的 $rq^e$ ，并且用一个字典存下这两个数值对 $\left\{rq^e:rp\right\}$ ，然后枚举 $rq$ ，相同的方法计算 $rp$ ，然后查询数值对 $\left\{rq^e:rp\right\}$ 是否存在，存在说明找到了

	#求 rp 和 rq, 中途相遇攻击
	n_=122146249659110799196678177080657779971
	c_=90846368443479079691227824315092288065-0xdeadbeef
	e=65537
	dirct={}
	for rp in range(2**24):
	rqe=c_-pow(rp,e,n_)
	dirct[rqe]=rp

	for rq in range(2**24):
	if pow(rq,e,n_) in dirct.keys():
	print("rp=",dirct[pow(rq,e,n_)])
	print("rq=",rq)
	break
	#rq= 11974933
	#rp= 405771

然后接下来就要解出 $pp$ 和 $qq$ 了

$n=pp\times qq=(p+rp)(q+rq)=(a^4+rp)(b^4+rq)$

注意到 $a,b\in [0,2^{256})$ ，而 $rp,rq\in [0,2^{24})$ ，因此 $a,b >> rp,rq$ ，所以 $n$ 可以近似成 $a^4b^4$ ，所以 $ab=\lfloor n^{\frac{1}{4}} \rfloor$ ，令 $a^4b^4=pq=t^4$ ，接下来展开 $n$

$n=(p+rp)(q+rq)=t+prq+qrp+rprq\\ np=pt+p^2rq+trp+prprq\\ p^2rq+p(t+rqrp-n)+trp=0$

解一元二次方程即可

	import gmpy2
	from Crypto.Util.number import *
	e=65537
	rq= 11974933
	rp= 405771
	n = 3183573836769699313763043722513486503160533089470716348487649113450828830224151824106050562868640291712433283679799855890306945562430572137128269318944453041825476154913676849658599642113896525291798525533722805116041675462675732995881671359593602584751304602244415149859346875340361740775463623467503186824385780851920136368593725535779854726168687179051303851797111239451264183276544616736820298054063232641359775128753071340474714720534858295660426278356630743758247422916519687362426114443660989774519751234591819547129288719863041972824405872212208118093577184659446552017086531002340663509215501866212294702743
	enc_flag = 48433948078708266558408900822131846839473472350405274958254566291017137879542806238459456400958349315245447486509633749276746053786868315163583443030289607980449076267295483248068122553237802668045588106193692102901936355277693449867608379899254200590252441986645643511838233803828204450622023993363140246583650322952060860867801081687288233255776380790653361695125971596448862744165007007840033270102756536056501059098523990991260352123691349393725158028931174218091973919457078350257978338294099849690514328273829474324145569140386584429042884336459789499705672633475010234403132893629856284982320249119974872840
	t=pow(gmpy2.iroot(n,4)[0],4)

	a=rq
	b=t+rp*rq-n
	c=t*rp

	delta=b*2-4a*c
	print(a)
	print(b)
	print(c)
	roots=gmpy2.iroot(delta,2)
	if roots[1]==True:
	p=(roots[0]-b)//(2*a)
	pp=p+rp
	qq=n//pp
	L=(pp-1)*(qq-1)
	d=gmpy2.invert(e,L)
	m=pow(enc_flag,d,n)
	print(long_to_bytes(m))
	# ACTF{lsb_attack_in_RSA\|a32d7f}

密码学

# ACTF :Impossible rsa

# 知识点

# Problem

# Solve

# ACTF:leak_rsa

# 知识点

# Problem

Sage的使用

BUU_Crypto