526互联

CTFtime—有趣比赛题目收集(持续更新中)

发布时间 2023-11-06 08:46:20作者: Kicky_Mu

BlueHens CTF 2023（蓝母鸡CTF）

RSA School 5th Grade

Tags: small-e crypto rsa  

This is what we're given:

from Crypto.Util.number import *
msg=b"UDCTF{REDACTED}"
pt=bytes_to_long(msg)
p=getPrime(1024)
q=getPrime(1024)
N=p*q
e=3
ct=pow(pt,e,N)

print(N)
print(e)
print(ct)
#N=19071553514906413228005623880868413172589438760530345745552708038769515697875361787053550188848159274987925247955174211167277615747329764460652862539122337714189780686582390326881171096308885109154336023212767779863472386169665627283720649094479648444588259600544834704143105214853522264311830387911281263299214052701109619722665736303738110883886917231219876629681611411323913511707032906816948757362133848480976586951323342448069343747851239877539085111823678094070778241732994351072251605007909682674187665596109353312252881532685577047967768366217935948525094732268620589271065304471832191222326947334404799847563
#e=3
#ct=270903177796878498388304376598565799121492331770875203351555502784804760985678087802688162298096409297508110557051747972509915173895153270896299567072600809265143377905255294763705268648639628042173298874918538565864469546919085252896111245679898930789

小明文

exp:

import gmpy2
from Crypto.Util.number import long_to_bytes
n=19071553514906413228005623880868413172589438760530345745552708038769515697875361787053550188848159274987925247955174211167277615747329764460652862539122337714189780686582390326881171096308885109154336023212767779863472386169665627283720649094479648444588259600544834704143105214853522264311830387911281263299214052701109619722665736303738110883886917231219876629681611411323913511707032906816948757362133848480976586951323342448069343747851239877539085111823678094070778241732994351072251605007909682674187665596109353312252881532685577047967768366217935948525094732268620589271065304471832191222326947334404799847563
e=3
c=270903177796878498388304376598565799121492331770875203351555502784804760985678087802688162298096409297508110557051747972509915173895153270896299567072600809265143377905255294763705268648639628042173298874918538565864469546919085252896111245679898930789

m = gmpy2.iroot(c, 3)[0]
print(long_to_bytes(m))
#UDCTF{0k_m4yb3_d0nt_u5e_e_3qu4l5_3}

RSA School 4th Grade

This is what we're given:

from Crypto.Util.number import *
e=65537
your_e = getPrime(20)
msg=bytes_to_long(b'UDCTF{REDACTED}')
p=getPrime(512)
q=getPrime(512)
n=p*q
assert(msg < n)
ct=pow(msg, e, n)
your_d = inverse(your_e, (p-1)*(q-1))
print(your_e)
print(your_d)
print(n)
print(e)
print(ct)

Use the provided RSA textbook -- https://bitsdeep.com/posts/attacking-rsa-for-fun-and-ctf-points-part-1/ -- it really helps!(参考这本RSA教科书是真的有帮助的嘿嘿！)

exp:

from Crypto.Util.number import long_to_bytes
your_e=548861
your_d=95173232432571941329231712692828118443780574466702093807146321250099677631827067825710345421542241500117509827717221625523077656554170307232963298108032249257829668442277402436905496971410095631707035128294281318370127935482352287840967522858886054571972660826718745245567014905338023490270530223206547055189
n=128923276994737790032784225847154420815473322545569053376748335367791339027988282369445542202224938698537424444443434684524386629219697192340629226569242894844874718895350330788650992608621499779776079293063355076268941953990983854217613662005027668855183281795022629934463967333582234624036115283306256019477
e=65537
c=101925091511033045433108849975441961999589763870098425244810307722908781911184299892072334641669931066841662878745617845011689451171244453969963211155840837507751273716371760271643490363012983256424608885239953158409708266675819028960222627654995967984657602529298637614235721996131897162063485544360691578861

phi = 0
k = (your_e * your_d - 1) // n
for i in range(1000000):
    if (your_e * your_d - 1) % k == 0:
        # right value of phi found
        phi = (your_e * your_d - 1) // k
        break
    k += 1

d = pow(e, -1 ,phi)
m = pow(c, d, n)
print(long_to_bytes(m))
#UDCTF{m0d_mult1pl1c4tiv3_inv3r5e_nd_57uff}

RSA School 3rd Grade

This is what we're given：

from Crypto.Util.number import *
p=getPrime(512)
q=getPrime(512)
n=p*q
e1=71
e2=101
msg=bytes_to_long(b'UDCTF{REDACTED}')
c1 = pow(msg, e1, n)
c2 = pow(msg, e2, n)
print(n)
print(e1)
print(e2)
print(c1)
print(c2)
#n=87587426608653108851564813489752475287019321764561555461700901651463446024854423042554629096780987943450742890279417241231211446818009232077230407281610183609540264821974669679932743621434901779832901512681108061652309435608446510337833028029876549629818957952682516026313018526405972829923620377438164377109
#e1=71
#e2=101
#c1=1421275848974615267320815554113040672023972283807752574007971561416386636110464890632994733734995114229161525885389065244354678964389211537085513310823751266472044865745324866096898051759507738772227296453397678055024824805366251635154522059070310922367078281343183508274450904681187384450253350434931649011
#c2=26097095086985946477598349002260598942399303275420948828501512467473619292573670218058274201990116295246084096584962695127706609264424951086000719935218496250047555039460733768633688410770610612614744411304261153778159881980276162174277085197608466835857196307432992312260307797540746411319330318058866868362

We're given two ciphertexts. According to the given RSA textbook, it seems like we can just solve this by solving Bezout's identity!
This comes from the following proof:（我们得到了两个密文。根据给定的RSA教科书，我们似乎可以通过求解Bezout的恒等式来解决这个问题!
这来自以下证明:）

If gcd(e1, e2) = 1, then according to Bezout's identity, there exist integers a and b such that a * e1 + b * e2 = 1.
Therefore, we have the following:
c1 = m ^ e1 (mod n) ==> c1 ^ a = m ^ (e1 * a) (mod n)
c2 = m ^ e2 (mod n) ==> c2 ^ b = m ^ (e2 * b) (mod n)
c1 * c2 = m ^ (e1 * a + e2 * b) (mod n) = m ^ 1 (mod n)

Therefore, we just need to solve Bezout's identity to get m. In order to solve Bezout's identity, you can use the extended Euclid algorithm.
https://www.rookieslab.com/posts/extended-euclid-algorithm-to-find-gcd-bezouts-coefficients-python-cpp-code provides the code for the extended Euclid algorithm.

一眼丁真，共模n攻击。

expC:

n=87587426608653108851564813489752475287019321764561555461700901651463446024854423042554629096780987943450742890279417241231211446818009232077230407281610183609540264821974669679932743621434901779832901512681108061652309435608446510337833028029876549629818957952682516026313018526405972829923620377438164377109
e1=71
e2=101
c1=1421275848974615267320815554113040672023972283807752574007971561416386636110464890632994733734995114229161525885389065244354678964389211537085513310823751266472044865745324866096898051759507738772227296453397678055024824805366251635154522059070310922367078281343183508274450904681187384450253350434931649011
c2=26097095086985946477598349002260598942399303275420948828501512467473619292573670218058274201990116295246084096584962695127706609264424951086000719935218496250047555039460733768633688410770610612614744411304261153778159881980276162174277085197608466835857196307432992312260307797540746411319330318058866868362

# 已知两者n相同，e不同，共模攻击
#  c= m^e mod n
import gmpy2
from Crypto.Util.number import isPrime, sieve_base as primes, long_to_bytes

def egcd(a, b):
    if b == 0:
        return a, 0;
    else:
        x, y = egcd(b, a % b)
        return y, x - (a // b) * y  # 扩展欧几里得算法

s = egcd(e1, e2)
s1 = s[0]
s2 = s[1]
print(s[0], s[1])
m = gmpy2.powmod(c1, s1, n) * gmpy2.powmod(c2, s2, n) % n

print(long_to_bytes(m))
#UDCTF{3uc1id_th4_60at}

 expA:

def extended_euclid_gcd(a, b):
    """
    Returns a list `result` of size 3 where:
    Referring to the equation ax + by = gcd(a, b)
        result[0] is gcd(a, b)
        result[1] is x
        result[2] is y
    """
    s = 0; old_s = 1
    t = 1; old_t = 0
    r = b; old_r = a

    while r != 0:
        quotient = old_r//r # In Python, // operator performs integer or floored division
        old_r, r = r, old_r - quotient*r
        old_s, s = s, old_s - quotient*s
        old_t, t = t, old_t - quotient*t
    return [old_r, old_s, old_t]

n=87587426608653108851564813489752475287019321764561555461700901651463446024854423042554629096780987943450742890279417241231211446818009232077230407281610183609540264821974669679932743621434901779832901512681108061652309435608446510337833028029876549629818957952682516026313018526405972829923620377438164377109
e1=71
e2=101
c1=1421275848974615267320815554113040672023972283807752574007971561416386636110464890632994733734995114229161525885389065244354678964389211537085513310823751266472044865745324866096898051759507738772227296453397678055024824805366251635154522059070310922367078281343183508274450904681187384450253350434931649011
c2=26097095086985946477598349002260598942399303275420948828501512467473619292573670218058274201990116295246084096584962695127706609264424951086000719935218496250047555039460733768633688410770610612614744411304261153778159881980276162174277085197608466835857196307432992312260307797540746411319330318058866868362

#ax + by = 1
gcd, x, y = extended_euclid_gcd(e1, e2)
m = (pow(c1, x, n) * pow(c2, y, n)) % n
m = format(m, 'x')
for i in range(0, len(m), 2):
    print(chr(int(m[i:i+2], 16)), end='')
#UDCTF{3uc1id_th4_60at}