海南大学CTF密码题

三道密码题全是RSA的加密，也算是有缘，毕竟目前为止唯一写过代码实现的就是RSA，而且解题过程也让我想起了小时候学习除法时那些关系，再次说一下这次学到的一个比较有用的库gmpy2，这个库所能处理的大数比python本身更强大，想RSA这种秘钥很长的加密算法，就算是python也很难精确，而有了gmpy2就不一样了，处理的很完美。

第一题很基础的RSA，给了密文27565231154623519221597938803435789010285480123476977081867877272451638645710

然后给了加密用的脚本

from binascii import a2b_hex,b2a_hex

flag = "***************************"
p = 262248800182277040650192055439906580479
q = 262854994239322828547925595487519915551

e = 65533
n = p*q

c = pow(int(b2a_hex(flag.encode()),16),e,n)
#
print(c)

然后我们根据rsa的原理，知道pq就能得到 φ(n) = (p-1)*(q-1)，然后私钥d可以根据 (e*d) % fn = 1来反推私钥d，再通过c的d次幂 % n 来得到明文m，之后，我们看淡源码中有16进制编码，最后还需要逆回去，下面是逆运算脚本

from binascii import a2b_hex,b2a_hex
import gmpy2

p = 262248800182277040650192055439906580479
q = 262854994239322828547925595487519915551

e = 65533
n = p*q
c = 27565231154623519221597938803435789010285480123476977081867877272451638645710
fn = (p-1)*(q-1)
d = gmpy2.invert(e,fn)

m = pow(c,int(d),n)
z = str(hex(m))[2:]
print(a2b_hex(z))
# 得到flag{B4by_Rs4}

第二题比第一题的难度稍微高了点给出了一部分信息

p = 177077389675257695042507998165006460849
n = 37421829509887796274897162249367329400988647145613325367337968063341372726061
c = ==gMzYDNzIjMxUTNyIzNzIjMyYTM4MDM0gTMwEjNzgTM2UTN4cjNwIjN2QzM5ADMwIDNyMTO4UzM2cTM5kDN2MTOyUTO5YDM0czM3MjM

还有代码的脚

from base64 import b64encode as b32encode
from gmpy2 import invert,gcd,iroot
from Crypto.Util.number import *
from binascii import a2b_hex,b2a_hex
import random

flag = "******************************"

nbit = 128

p = getPrime(nbit)
q = getPrime(nbit)
n = p*q

print p
print n

phi = (p-1)*(q-1)

e = random.randint(50000,70000)

while True:
	if gcd(e,phi) == 1:
		break;
	else:
		e -= 1;

c = pow(int(b2a_hex(flag),16),e,n)

print b32encode(str(c))[::-1]

我们不难看出，这里的公钥e是随机给出的，给的是50000到70000的一个随机数，而e如果和 φ(n) 互质，就用e来当做公钥，否则就让e逐渐向下相减，经过测试，我们发现从50000开始往下减，最近的e是49999，也就是说可以从49999到70000所有能当公钥的挨个尝试，注意一下，最后给出来的密文c实际是base64加密后的，千万别被base32给迷惑贴上解密脚本

import gmpy2
import binascii

q = gmpy2.mpz(211330365658290458913359957704294614589)
p = gmpy2.mpz(177077389675257695042507998165006460849)
n = gmpy2.mpz(37421829509887796274897162249367329400988647145613325367337968063341372726061)
c = gmpy2.mpz(2373740699529364991763589324200093466206785561836101840381622237225512234632)
fn = gmpy2.mpz((q-1)*(p-1))
x = range(49999,70001)
x = x[::-1]
a = []

for i in x:
    if gmpy2.gcd(i, fn) == 1:
        a.append(i)


for e in a:
    d = gmpy2.invert(e,fn)
    m = pow(c,d,n)
    z = hex(m)[2:]
    if z[:8] == "666c6167":
        break
print(binascii.unhexlify(z))
# 得到flag{rs4_1s_s1mpl3!#}

我们的q是根据p和n计算出来的，q = n / p，然后49999到70000中所有能用来当公钥的都进行尝试，然后计算出d，再计算明文，因为计算结果是10进制，所以我们转为16进制，然后用前8位与flag转化的16进制进行比较，如果相同就得到flag

第三题其实更容易，因为不需要自己写代码，用共膜攻击即可，放上题目下载链接http://only.lich.xin/wp-content/uploads/2019/05/RSA密码3.zip

然后给出一位大佬的详细解释https://www.jianshu.com/p/2d95bdd0fb0d?from=timeline&isappinstalled=0

最后就是解题代码

import sys, gmpy2, base64
from binascii import unhexlify

def egcd(a, b):
    if a == 0:
        return (b, 0, 1)
    else:
        g, y, x = egcd(b % a, a)
    return (g, x - (b // a) * y, y)


def modinv(a, m):
    g, x, y = egcd(a, m)
    if g != 1:
        raise Exception('modular inverse does not exist')
    else:
        return x % m


def pad_even(x):  # 重要！凑齐2位，将0x1 变成 0x01
    return ('', '0')[len(x) % 2] + x


def CipherB2n(c):  # 将base64编码后的密文转成数字
    c2 = base64.b64decode(c)
    temp = ''
    for i in c2:
        temp += pad_even(str(hex(i))[2:])
    temp = eval('0x' + temp)
    return (temp)


def CipherN2b(m):  # 将数字转换成ascii
    hex_m = hex(m)[2:]
    if hex_m[-1] == 'L':
        hex_m = hex_m[:-1]
    return hex_m


if __name__ == '__main__':

    sys.setrecursionlimit(1000000)
    e1 = 2333  # 根据分解结果
    e2 = 23333  # 根据分解结果
    s = egcd(e1, e2)
    s1 = s[1]
    s2 = s[2]
    c1 = 'R3Noy6r3WLItytAmb4FmHEygoilucEEZbO9ZYXx5JN03HNpBLDx7fXd2fl+UL5+11RCs/y0qlTGURWWDtG66eNLzGwNpAKiVj6I7RtUJl2Pcm3NvFeAFwI9UsVREyh7zIV6sI9ZP8l/2GVDorLAz5ULW+f0OINGhJmZm8FL/aDnlfTElhQ87LPicWpXYoMtyr6WrxjK6Ontn8BqCt0EjQ7TeXZhxIH9VTPWjDmFdmOqaqdVIT+LZemTgLNESwM5nn4g5S3aFDFwj1YiDYl0/+8etvKfOrfoKOwR0CxsRHagwdUUTES8EcHLmMGCxCkDZn3SzmmA6Nb3lgLeSgG8P1A=='
    c2 = 'O+rRCXI3aTB6P1rYIOPUdalUp6ujpwEq4I20CoWA+HIL8xxGtqY6N5gpr0guZv9ZgOEAMFnBxOqMdVNnB9GgnhmXtt1ZWydPqIcHvlfwpd/Lyd0XSjXnjaz3P3vOQvR71cD/uXyBA0XPzmnTIMgEhuGJVFm8min0L/2qI7wg/Z7w1+4mOmi655JIXeCiG23ukDv6l9bZuqfGvWCa1KKXWDP31nLbp0ZN2obUs6jEAa1qVTaX6M4My+sks+0VvHATrAUuCrmMwVEivqIJ/nS6ymGVERN6Ohnzyr168knEBKOVj0FAOx3YLfppMM+XbOGHeqdKJRLpMvqFXDMGQInT3w=='
    c1 = CipherB2n(c1)
    c2 = CipherB2n(c2)
    # print hex(c1)
    n = 14853081277902411240991719582265437298941606850989432655928075747449227799832389574251190347654658701773951599098366248661597113015221566041305501996451638624389417055956926238595947885740084994809382932733556986107653499144588614105694518150594105711438983069306254763078820574239989253573144558449346681620784979079971559976102366527270867527423001083169127402157598183442923364480383742653117285643026319914244072975557200353546060352744263637867557162046429886176035616570590229646013789737629785488326501654202429466891022723268768841320111152381619260637023031430545168618446134188815113100443559425057634959299  # 共n
    if s1 < 0:
        s1 = - s1
        c1 = modinv(c1, n)
    elif s2 < 0:
        s2 = - s2
        c2 = modinv(c2, n)
    m = (pow(c1, s1, n) * pow(c2, s2, n)) % n
    print(unhexlify(CipherN2b(m)))
# 得到flag{23re_SDxF_y78hu_5rFgS}