[RSA2]P1

加密代码如下

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
flag = b'NSSCTF{******}'

p = getPrime(5120)
q = getPrime(5120)

n = p*q
e = 97
phi = (p-1)*(q-1)

m = bytes_to_long(flag)
c = powmod(m, e, n)

print(f'n = {n}')
print(f'e = {e}')
print(f'c = {c}')

我们发现e很小，所以我们尝试使用小明文去解决

要注意，iroot的[0]是结果[1]是能否做到

[RSA2]P2

我们发现这次的e虽然更小了，但是显然得不到

me<nm^{e} < n

又因为我们知道

c≡me mod Nc \equiv m^{e} \bmod N

所以我们可以得到

me≡c+k×Nm^{e} \equiv c+k\times N

因为e很小，所以我们可以通过枚举k来进行爆破
爆破代码如下

1
2
3
4
for i in range(1000):
    c1 = c + i*n
    if gmpy2.iroot(c1,e)[1]:
        print(long_to_bytes(gmpy2.iroot(c1,e)[0]))

[RSA2]P3

rabin板子题，直接打就行

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
from Crypto.Util.number import *
from gmpy2 import *

p = 67711062621608175960173275013534737889372437946924512522469843485353704013203
q = 91200252033239924238625443698357031288749612243099728355449192607988117291739
e = 2
c = 5251890478898826530186837207902117236305266861227697352434308106457554098811792713226801824100629792962861125855696719512180887415808454466978721678349614

def rabin_attack(c, n, p, q):
    c1 = powmod(c, (p+1)//4, p)
    c2 = powmod(c, (q+1)//4, q)
    cp1 = p - c1
    cp2 = q - c2

    t1 = invert(p, q)
    t2 = invert(q, p)

    m1 = (q*c1*c2 + p*c2*t1) % n
    m2 = (q*c1*t2 + p*cp2*t1) % n
    m3 = (q*cp1*t2 + p*c2*t1) % n
    m4 = (q*cp1*t2 + p*cp2*t1) % n

    return m1, m2, m3, m4

ms = rabin_attack(c, p*q, p, q)

for m in ms:
    print(long_to_bytes(m))

[RSA2]P4

源码如下

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
from Crypto.Util.number import *
from gmpy2 import *

flag = b'NSSCTF{******}'

p = getPrime(256)
q = getPrime(256)

n = p*q
d = getPrime(128)
e = inverse(d, (p-1)*(q-1))
m = bytes_to_long(flag)

c = powmod(m, e, n)

print(f'n = {n}')
print(f'e = {e}')
print(f'c = {c}')

我们发现e变成了d与phi的逆元，经过推理之后发现e/phi可以近似等于k/d，而且这里的e很大，所以我们可以考虑使用维纳攻击，也就是对于e/phi进行连分数展开
解题脚本如下

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
from Crypto.Util.number import *
from gmpy2 import *

n = 6969872410035233098344189258766624225446081814953480897731644163180991292913719910322241873463164232700368119465476508174863062276659958418657253738005689
e = 3331016607237504021038095412236348385663413736904453330557803644384818257225138777641344877202234881627514102078530507171735156112302207979925588113589669
c = 1754994938947260364311041300467524420957926989584983693004487724099773647229373820465164193428679197813476633649362998772470084452129370353136199193923837

class ContinuedFraction():
    def __init__(self, numerator, denumerator):
        self.numberlist = []  # number in continued fraction
        self.fractionlist = []  # the near fraction list
        self.GenerateNumberList(numerator, denumerator)
        self.GenerateFractionList()

    def GenerateNumberList(self, numerator, denumerator):
        while numerator != 1:
            quotient = numerator // denumerator
            remainder = numerator % denumerator
            self.numberlist.append(quotient)
            numerator = denumerator
            denumerator = remainder

    def GenerateFractionList(self):
        self.fractionlist.append([self.numberlist[0], 1])
        for i in range(1, len(self.numberlist)):
            numerator = self.numberlist[i]
            denumerator = 1
            for j in range(i):
                temp = numerator
                numerator = denumerator + numerator * self.numberlist[i - j - 1]
                denumerator = temp
            self.fractionlist.append([numerator, denumerator])


a = ContinuedFraction(e, n)
for k, d in a.fractionlist:
    m = powmod(c, d, n)
    flag = long_to_bytes(m)
    
    if b'NSSCTF' in flag:
        print(flag)

[RSA2]P5

加密代码如下

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
from Crypto.Util.number import *
import os

flag = os.getenv('FLAG')
m = bytes_to_long(flag.encode())
e = 127

def enc():
    p = getPrime(512)
    q = getPrime(512)
    n = p*q
    c = pow(m, e, n)
    print(f"n: {n}")
    print(f"c: {c}")

def main():
    while True:
        opt = int(input('input> '))
        if opt == 1:
            enc()

main()

它给了n，c那么我们就可以推导出

c=k×n+mec = k \times n + m^{e}

既然它给了我c和n，e也是已知的，我们又已知部分明文，那么我们可以尝试遍历k找到使得符合部分明文的k即可
事实证明这种做法是错的
那么我们可以考虑使用中国剩余定理去求解，也就是如果有多个同余式，我们可以使用crt来求解他们的共同明文
脚本如下

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
p = remote("node4.anna.nssctf.cn",29000)
e = 127
n_ed = []*64
c_ed = []*64
for i in range(64):
    p.sendline("1")
    n_un = p.recvline().decode()
    c_un = p.recvline().decode()
    n = int(re.findall("n: (\d+)",n_un)[0])
    c = int(re.findall("c: (\d+)",c_un)[0])
    n_ed.append(n)
    c_ed.append(c)

me = crt(n_ed,c_ed)[0]
m = gm/imagesot(me,e)[0]
print(long_to_bytes(m))

[RSA2]P6

加密代码如下

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
from Crypto.Util.number import *
from random import choice

flag = b'NSSCTF{******}'

def getMyPrime(nbits):
    while True:
        p = 1
        while p.bit_length() <= nbits:
            p *= choice(sieve_base)
        
        if isPrime(p+1):
            return p+1

p = getMyPrime(256)
q = getMyPrime(256)

n = p*q
e = 65537
m = bytes_to_long(flag)

c = pow(m, e, n)

print(f'n = {n}')
print(f'e = {e}')
print(f'c = {c}')

'''
n = 53763529836257082401813045869248978487210852880716446938539970599235060144454914000042178896730979463959004404421520555831136502171902051936080825853063287829
e = 65537
c = 50368170865606429432907125510556310647510431461588875539696416879298699197677994843344925466156992948241894107250131926237473102312181031875514294014181272618
'''

我们进到这个sieve_base里看

发现这个是10000个素数，所以p就是n个小素数的乘积+1，那么我们可以得知，p-1就是个n-smooth数，根据光滑数的性质我们可以得知

gcd(ak!−1,n)=pgcd(a^{k!}-1,n) = p

所以我们可以尝试遍历这个k，来分解n
而我们也不需要每次都计算这个x!的值，可以直接通过模的性质来计算

ax+1!≡(ax!mod  n)x+1(mod  n)a^{x+1!}\equiv (a^{x!}\mod n)^{x+1}(\mod n)

那么我们的解密脚本就如下

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
n = 53763529836257082401813045869248978487210852880716446938539970599235060144454914000042178896730979463959004404421520555831136502171902051936080825853063287829
e = 65537
c = 50368170865606429432907125510556310647510431461588875539696416879298699197677994843344925466156992948241894107250131926237473102312181031875514294014181272618

a = 2
m = 2
while True:
    a = pow(a, m, n)
    p = GCD(a-1, n)
    if p != 1 and p != n:
        break
    m += 1

q = n // p

phi = (p-1)*(q-1)
d = inverse(e, phi)
m = pow(c, d, n)
print(long_to_bytes(m))

[RSA2]P7

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
from Crypto.Util.number import *
from random import choice

flag = b'NSSCTF{******}'

def getMyPrime(nbits):
    while True:
        p = 1
        while p.bit_length() <= nbits:
            p *= choice(sieve_base)
        
        if isPrime(p-1):
            return p-1

p = getMyPrime(256)
q = getMyPrime(256)

n = p*q
e = 65537
m = bytes_to_long(flag)

c = pow(m, e, n)

print(f'n = {n}')
print(f'e = {e}')
print(f'c = {c}')

加密脚本如上
这次是变成了p+1是一个b-smooth数
p+1光滑就是使用了卢卡斯序列扩展得到了一个p的倍数，然后与n求公因数从而分解n
代码如下

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
from Crypto.Util.number import *
from gmpy2 import *
from itertools import count

n = 63398538193562720708999492397588489035970399414238113344990243900620729661046648078623873637152448697806039260616826648343172207246183989202073562200879290937
e = 65537
c = 26971181342240802276810747395669930355754928952080329914687241779532014305320191048439959934699795162709365987652696472998140484810728817991804469778237933925

def mlucas(v, a, n):
    v1, v2 = v, (v ** 2 - 2) % n
    for bit in bin(a)[3:]: v1, v2 = ((v1 ** 2 - 2) % n, (v1 * v2 - v) % n) if bit == "0" else (
        (v1 * v2 - v) % n, (v2 ** 2 - 2) % n)
    return v1

def primegen():
    yield 2
    yield 3
    yield 5
    yield 7
    yield 11
    yield 13
    ps = primegen()  # yay recursion
    p = ps.__next__() and ps.__next__()
    q, sieve, n = p ** 2, {}, 13
    while True:
        if n not in sieve:
            if n < q:
                yield n
            else:
                next, step = q + 2 * p, 2 * p
                while next in sieve:
                    next += step
                sieve[next] = step
                p = ps.__next__()
                q = p ** 2
        else:
            step = sieve.pop(n)
            next = n + step
            while next in sieve:
                next += step
            sieve[next] = step
        n += 2

def ilog(x, b):  # greatest integer l such that b**l <= x.
    l = 0
    while x >= b:
        x /= b
        l += 1
    return l

def attack(n):
    for v in count(1):
        for p in primegen():
            e = ilog(isqrt(n), p)
            if e == 0:
                break
            for _ in range(e):
                v = mlucas(v, p, n)
            g = gcd(v - 2, n)
            if 1 < g < n:
                return int(g), int(n // g)  # g|n
            if g == n:
                break

p, q = attack(n)


phi = (p-1)*(q-1)
d = invert(e, phi)
m = powmod(c, d, n)
print(long_to_bytes(m))

[RSA2]P8

我们的目的也就是找出一个可以使得

s1×e1+s2×e2=1s_{1}\times e_{1} + s_{2}\times e_{2} = 1

那么我们就可以使得c1xc2=m mod n
我们也就可以据此求得m
这里要使用欧几里得扩展算法，具体代码如下

1
2
3
4
5
6
7
8
9
10
11
12
13
from Crypto.Util.number import *
from gmpy2 import *

n = 120294155186626082670474649118722298040433501930335450479777638508444129059776534554344361441717048531505985491664356283524886091709370969857047470362547600390987665105196367975719516115980157839088766927450099353377496192206005171597109864609567336679138620134544004766539483664270351472198486955623315909571
e1 = 38317
e2 = 63409
c1 = 42703138696187395030337205860503270214353151588149506110731264952595193757235229215067638858431493587093612397165407221394174690263691095324298012134779703041752810028935711214038835584823385108771901216441784673199846041109074467177891680923593206326788523158180637665813642688824593788192044139055552031622
c2 = 50460092786111470408945316270086812807230253234809303694007902628924057713984397041141665125615735752600114964852157684904429928771531639899496987905067366415806771003121954852465731110629459725994454904159277228514337278105207721011579794604761255522391446534458815389983562890631994726687526070228315925638

_, s1, s2 = gcdext(e1, e2)

m = powmod(c1, s1, n)*powmod(c2, s2, n) % n
print(long_to_bytes(m))

[RSA2]P9

dp&&dq泄露的题目，我们直接用板子打

1
2
3
4
5
6
7
8
9
10
11
12
13
14
from Crypto.Util.number import *
from gmpy2 import *

p = 13070310882303377463944295715444821218324151935347454554272870042925400761984585838979931730897626589859098834802923539617244712852188293321626061072925723
q = 10411551818233737389114520103233235272671271111546186997024935593000298916988792710521511848414549553426943998093077337023514210631662189798921671306236009
c = 62492280219693914005334023569480350249964827909276875032578276064973191654731196407886841145547165693859745313398152742796887457192397932684370631253099255490064673499746314452067588181106154875239985334051909867580794242253066085627399488604907196244465911471895118443199543361883148941963668551684228132814
dp = 11568639544706374912496682299967972464196129347160700749666263275305083977187758414725188926013198988871173614336707804756059951725809300386252339177953017
dq = 3455040841431633020487528316853620383411361966784138992524801280785753201070735373348570840039176552952269927122259706586236960440300255065994052962742469

invp = invert(p, q)
m1 = powmod(c, dp, p)
m2 = powmod(c, dq, q)
m = (((m2 - m1)*invp) % q)*p + m1
print(long_to_bytes(m))

[RSA2]P10

单纯的dp泄露，我们可以通过

e×d≡1mod  ϕ(n)e\times d \equiv 1 \mod \phi(n)

然后发现

dp×e≡1mod  (p−1)d_{p}\times e \equiv 1 \mod (p-1)

然后因为dp<p-1 所以有k<e，那么我们可以直接遍历找到k

1
2
3
4
5
6
7
8
9
10
11
12
13
14
# 10
n = 79201858340517902370077926747686673001645933420450220163567700296597652438275339093680329918615445030212417351430952656177171126427547284822789947152085534939195866096891005587613262293569611913019639653984932469691636338705418303482885987114085769045348074530172292982433373154900841135911548332400167290083
c = 70109332985937768446301118795636999352761371683181615470371772202170324747707233792154935611826981798791499937601162039878070094663516868746240133223110650205575807753345252087103328657073552992431511929172241702073381723302143955977662087561904058172777520360991685289300855900793806183473523998422682944404
dp = 3098334089252415941833934532457314870210700261428241562420857845879512952043729097866485406309479489101668423603305497982177150304625615059119312238777275
e = 65537
for i in range(1,e):
    if (e * dp - 1) % i == 0:
        p = ((e * dp - 1) // i ) +1
        print(p)
        if n % p == 0:
            q = n // p
            print(q)
            d = inverse(e,(p-1)*(q-1))
            exit(long_to_bytes(pow(c,d,n)))

[RSA2]P11

这里的e较大，我们不能尝试直接遍历了，根据之前的欧拉降幂加上这个，我们可以推出来

aedp−a≡0mod  pa^{ed_{p}}-a\equiv 0 \mod p

所以我们可以直接将这个式子和n取gcd即可得到p
我们利用这个方法写脚本

1
2
3
4
5
6
7
8
9
10
n = 108280026722298796068968170303156759745471686664814404724171434502249429011870583595808692893118419248225924869164875379709992190884930717654004006466664403479467573176438601715156464950045121937338569942817256182277141174728470067308962244296992229214749863655518517510026063088263849891990324547823192559069
e = 305691242207901867366357529364270390903
c = 26537258289122728220745496185201994733321402056894636636642710319261241111675937946139938310952968353253866895253865273981912174303818938005932883052177988834834575591342856235464380238486868448329727891268391728758132913642966389278296932186703733187105516710825918064228397602264185334108934765627411913661
dp = 2656631506624565349527023729530989647164022271235521672257622068579788839123502046687139927161669209201953909023994372208117081512139181611949631467292513

m = 10007
p = GCD(pow(m,e*dp,n)-m,n)
q = n // p 
d = inverse(e,(p-1)*(q-1))
print(long_to_bytes(pow(c,d,n)))

[RSA2]P12

d泄露，本质就是找了一个数同时是p-1和phi的倍数

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
from Crypto.Util.number import *
from gmpy2 import *
import hashlib

n = 113917408220469425995764932761465306974540330325378601642830241920567032775895088098706711486764203845425248022960733155994427766750033219106642310531864450654102562104771892268897793145789045570107312401570269581223945259704851104645493075550316424129401227653740942495625720165869565257394427181127734628103
d = 15762135247924329080208071933121250646888501386858311483546464344350547831176536290630826247188272280853810047335214127264865205744683174860903496832368687060941437002920094364116706593296591581117381565805322046922482804679245558495134876677733584718947309975077159564300049936769192724856722338627154192353
e = 65537


t = e*d - 1
s = 0

while t % 2 == 0:
    s += 1
    t //= 2

found = False

for i in range(1, s):
    c1 = powmod(2, powmod(2, i-1, n)*t, n)
    c2 = powmod(2, powmod(2, i, n)*t, n)
    if c1 != 1 and c1 != (-1 % n) and c2 == 1:
        p = gcd(c1 - 1, n)
        q = n // p
        break

if p > q:
    p, q = q, p

print('NSSCTF{%s}' % hashlib.md5(str(p).encode()).hexdigest())