2023 上海大学生网络安全赛 Twice

  1. 题目源码
  2. 分析
    1. two
    2. one
  3. 解题

题目源码

from Crypto.Util.number import *
from Crypto.Util.Padding import pad
from secret import flag, a0,a1,b0,b1

def gen_keys(k):
    p, q, r = getPrime(k), getPrime(k), getPrime(k)
    pubkey = p**2 * q * r
    n = pubkey
    phi = (p-1) * (q-1) * (r-1)
    privkey = inverse(n, phi)
    return pubkey, privkey
    
def encrypt(msg, pubkey):
    return pow(bytes_to_long(pad(msg,190)), pubkey, pubkey)

p = getPrime(512)
q = getPrime(512)
e = getPrime(128)
n1 = p*q
assert pow(a0,2) + e * pow(b0,2) == n1
assert pow(a1,2) + e * pow(b1,2) == n1
# one
m = bytes_to_long(flag)
c1 = pow(m, e, n1)
# two
pub,pri = gen_keys(512)
c2 = encrypt(long_to_bytes(c1),pub)

print("n1=",n1)
print("a0=",a0)
print("a1=",a1)
print("b0=",b0)
print("b1=",b1)
print("c2=",c2)
print("pub=",pub)
print("pri=",pri)

'''
n1= 87665217778729524993118310155129480311708534438704150676980835344891979982717119161254489670350577173938239682286759779547789055360697960379769693294306641200724257991678505629369338313581657539655057636732714452287023658150014746541718058750871927050204352584824130972892779877896415568548748364583880371427
a0= 9362970563807702423162361787386216886594085863490420184497563324865248429693287404341206766515622648778272030443641712923250846610046357375553046092690266
a1= 9362970563807702423162361745963275441706212437133735476965289880825874017106479792816846422940594285630367772490647779230476318907092613021181772527068514
b0= 74836747076024432741470938222753940689278814091833170112470104078475118700897724833941621360216319460657128947837095907483
b1= 93520964011413593176393772179429258741894666938448164504029535235899813670669478849381259720656022408302270582527720184427
c2= 7090659117351297531755883438960933877263181849815568437232708639999747137583085680350909771730266998763362206865224473283130982570816918537377058225538656521223617210560656370841094169187300346437355127376920626133248983100115455529533265136725274741407727211587363755394889303944789720637515498330115070515942678821608630620272575086220037432383957991049220528177053370450234486390431027269543481157974773863005279984438957464388749795275109730696430700744950555993640720758137888948464005039907816169108829675809911658280616090368129767282407708640291466242813209343944276906740181222776418701978734705056220412984
pub= 15393634704241437811571407047965218207529278849238950329420499882359515149154462592674433680412129087082275102567406550543503710118161775213536183656910892279726520148202227312448507629264239427121015706092403872586978266402316447553116208411724407465368711586887621447872002364407809592953543797319646692321612541334341183378900324146713189121105760280994702695266049904020810024990537652609099294535255399210219454610583930829883737909993183476961897889084229322415995483397484414924734020539093114397393070394929656598174957126771887906087335882580049097369036955153036983424389092042285637185882327630117320615769
pri= 424184707992085368727036634979681060339188016631126395371395132791009626692092220877797321952063158959159298372653275672949543326347146732580465753892335912633332743258010037527036987474957662424735475674152462914082526658466925646224968182493094690460023505421720259663381122409147914948696061450626153526908753546708693503710352787787701648821693599138777500334149879355898444355846028142814267511986218166066642222930494985736426837825122392760739011897554697
'''

分析

two

为了方便分析,先做以下定义

n = p**2 * q * r
phi = p * (p-1) * (q-1) * (r-1)

n_ = p * q * r
phi_ = (p-1) * (q-1) * (r-1)

c = pow(m, n, n),n和phi不互素,所以解密的时候就不能直接用n和phi,得用n_和phi_,而phi_已经给出,所以我们只需根据d = inverse(n, phi_)来求n_

\(nd \equiv 1 \mod{phi\_} \\ nd = 1 + k(p-1)(q-1)(r-1) \\ 2^{nd} = 2 \cdot 2^{k(p-1)(q-1)(r-1)} \\ 两边同时模n\_ \\ 2^{nd} \equiv 2 \cdot 2^{k(p-1)(q-1)(r-1)} \equiv 2 \mod{n\_} \\ 2^{nd} - 2 = k_1 n\_ \\ n\_ = \gcd(k_1 n\_,\ n) \\ m = c^d\ \%\ {n\_}\)

one

构造消去e

\(\because \begin{cases} n = a_0^2 + e b_0^2 \\ n = a_1^2 + e b_1^2 \end{cases} \\ n b_0^2 - n b_1^2 = (a_1^2 + e b_1^2)b_0^2 - (a_0^2 + eb_0^2)b_1^2 = a_1^2 b_0^2 - a_0^2 b_1^2 = (a_1 b_0 + a_0 b_1)(a_1 b_0 - a_0 b_1) \\ pq(b_0^2 - b_1^2) = (a_1 b_0 + a_0 b_1)(a_1 b_0 - a_0 b_1) \\ p = \gcd(n,\ a_1 b_0 + a_0 b_1) \\ q = \gcd(n\ ,a_1 b_0 - a_0 b_1)\)

解题

from Crypto.Util.number import *
from Crypto.Util.Padding import pad,unpad

n1= 87665217778729524993118310155129480311708534438704150676980835344891979982717119161254489670350577173938239682286759779547789055360697960379769693294306641200724257991678505629369338313581657539655057636732714452287023658150014746541718058750871927050204352584824130972892779877896415568548748364583880371427
a0= 9362970563807702423162361787386216886594085863490420184497563324865248429693287404341206766515622648778272030443641712923250846610046357375553046092690266
a1= 9362970563807702423162361745963275441706212437133735476965289880825874017106479792816846422940594285630367772490647779230476318907092613021181772527068514
b0= 74836747076024432741470938222753940689278814091833170112470104078475118700897724833941621360216319460657128947837095907483
b1= 93520964011413593176393772179429258741894666938448164504029535235899813670669478849381259720656022408302270582527720184427
c2= 7090659117351297531755883438960933877263181849815568437232708639999747137583085680350909771730266998763362206865224473283130982570816918537377058225538656521223617210560656370841094169187300346437355127376920626133248983100115455529533265136725274741407727211587363755394889303944789720637515498330115070515942678821608630620272575086220037432383957991049220528177053370450234486390431027269543481157974773863005279984438957464388749795275109730696430700744950555993640720758137888948464005039907816169108829675809911658280616090368129767282407708640291466242813209343944276906740181222776418701978734705056220412984
pub= 15393634704241437811571407047965218207529278849238950329420499882359515149154462592674433680412129087082275102567406550543503710118161775213536183656910892279726520148202227312448507629264239427121015706092403872586978266402316447553116208411724407465368711586887621447872002364407809592953543797319646692321612541334341183378900324146713189121105760280994702695266049904020810024990537652609099294535255399210219454610583930829883737909993183476961897889084229322415995483397484414924734020539093114397393070394929656598174957126771887906087335882580049097369036955153036983424389092042285637185882327630117320615769
pri= 424184707992085368727036634979681060339188016631126395371395132791009626692092220877797321952063158959159298372653275672949543326347146732580465753892335912633332743258010037527036987474957662424735475674152462914082526658466925646224968182493094690460023505421720259663381122409147914948696061450626153526908753546708693503710352787787701648821693599138777500334149879355898444355846028142814267511986218166066642222930494985736426837825122392760739011897554697

# two
n = pub
d = pri
n_ = GCD(pow(2, n*d, n) - 2, n)
c1 = bytes_to_long(unpad(long_to_bytes(pow(c2, d, n_)), 190))

# one
p = GCD(n1, a1*b0+a0*b1)
q = n1 // p
e = (n1 - a0**2) // b0**2
d = inverse(e, (p-1)*(q-1))
print(long_to_bytes(pow(c1, d, n1)))
# b'flag{1a100d2c0dab19c4430e7d73762b3423}'

转载请注明来源,欢迎对文章中的引用来源进行考证,欢迎指出任何有错误或不够清晰的表达。可以邮件至 skatexu@qq.com

文章标题:2023 上海大学生网络安全赛 Twice

字数:513

本文作者:skateXu

发布时间:2023-11-22, 16:19:00

最后更新:2023-12-15, 14:14:58

原始链接:http://example.com/2023/11/22/2023-%E4%B8%8A%E6%B5%B7%E5%A4%A7%E5%AD%A6%E7%94%9F%E7%BD%91%E7%BB%9C%E5%AE%89%E5%85%A8%E8%B5%9B-Twice/

版权声明: "署名-非商用-相同方式共享 4.0" 转载请保留原文链接及作者。