2020 SCUCTF 新生赛 crypto RSA wp

2020 SCUCTF 新生赛 crypto RSA wp

简介

记录自己第一次CTF比赛，内容为2020年scuctf新生赛的crypto部分。

RSA加密算法 由来

RSA是1977年由罗纳德·李维斯特（Ron Rivest）、阿迪·萨莫尔（Adi Shamir）和伦纳德·阿德曼（Leonard Adleman）一起提出的。当时他们三人都在麻省理工学院工作。RSA就是他们三人姓氏开头字母拼在一起组成的 。

算法原理

RSA公开密钥密码体制的原理是：根据数论，寻求两个大素数比较简单，而将它们的乘积进行因式分解却极其困难，因此可以将乘积公开作为加密密钥

算法详解

WP部分 1.BABY_RSA 题目描述

c = 892408374578063131162925795619920779766603018609992406621503024400320421262482556891045333045408815199768659578199823419716777827460090306221618906101139272423449131313434967763664295600593363990276765767066758967765012850672428517786210813209127040442832574380675662826137452780727264357
n = 17076697689025821279984148703479525857912324396375097877800474725170566885465833732966897433803722770843910606215420934526050277173030062927090405120718833473629930226217051580832179577629652910778242159108718885516149768995851175071714817922775555170553827627677999093195969471873530031984433631909841287167351534954860426002075822101506835880510505034002629168205724869128357383388034971402180363910826536064357845040799329301895842061729319929568340334416516796267886218679042058969927331452548377324349084816441144473807565907927986545026739667157223640848553663532280797054758912745891410981282851031085852562257
e = 3

from Crypto.Util.number import bytes_to_long, long_to_bytes, getPrime

p = getPrime(1024)
q = getPrime(1024)

e = 3

flag = b"scuctf{**************}"

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

print("n = ", n)
print("e = ", e)
print("c = ", c)

解法

看到e=3，首先想到小明文攻击。 小明文攻击：当e=3时，如果明文过小，导致明文的三次方仍然小于n，那么通过直接对密文三次开方，即可得到明文。 下面是解题代码（python）：

from Crypto.Util.number import bytes_to_long, long_to_bytes, getPrime
import gmpy2

c=
n=
e=3

m=gmpy2.iroot(c, 3)
print(m)
#flag=long_to_bytes(m)

2.RSA_2 题目描述

c = 7162732898109470668490761172640544970587920562229245172318483665877098759808623298921271357899945260719802967519239
n = 21280377217500047527333756734822477656202976970565771310208586426341167199342722337358334403397116963913950346969157
e = 0x10001

解法

利用在线网站http://factordb.com对n进行分解 解题代码（python）

from Crypto.Util.number import long_to_bytes
import gmpy2
n=
p=
q=
r=
e=0x10001
c= 
n=p*q*r

phi=(p-1)*(q-1)*(r-1)
d=gmpy2.invert(e,phi)
m=pow(c,d,n)
print(long_to_bytes(m))

RSA_3 题目描述

n = 91271647735744709097708757371810693819959773890255602892321052899291140524662404139036987856738557165460502348870154514187118388083897953512262523467951513248663220055679646915049292032986252072883347567763269025940548912246834125522235064649335386094011441612211361270863086815851273615300955370973053395447
c1 = 8473924177689385097361186953656797062650227841190040965380473377780644233766714939608585534305414668494659709275756172697799483669925043356688884324887478394528746881611781366747757023562008158800275672858865552852268001893
c2 = 8473924177689385097361186953656797062650227841190040969573197360345161215089076875501807117350711332682919389146002627145413765770680053006201105979670824332086933186715988612908312603963949643839015421185340358831260317777

from random import randint
from gmpy2 import *
from Crypto.Util.number import *

class RSA:
    def __init__(self, m, e):
        self.p, self.q = getPrime(512), getPrime(512)
        self.n = self.p * self.q
        self.m = m
        self.e = e

    def padding(self):
        return self.m + randint(1, 114514191981019260817)

    def encrypt(self, m):
        return pow(m, self.e, self.n)

flag = 'scuctf{*********************}'
m = bytes_to_long(flag)
Task = RSA(m, 3)
f = open("info.txt","w")
f.write('n = ' + str(Task.n) + '\n')
f.write('c1 = ' + str(Task.encrypt(Task.m)) + '\n')
f.write('c2 = ' + str(Task.encrypt(Task.padding())) + '\n')

解法

阅读代码，可以发现c2没有用处，而e=3，由此又想到小明文攻击。 解题代码：

from Crypto.Util.number import bytes_to_long, long_to_bytes, getPrime
import gmpy2

c1=
n=
e=3

m=gmpy2.iroot(c, 3)
print(m)
#flag=long_to_bytes(m)

参考文献 [1]百度百科 [2]https://blog.csdn.net/jijianshuai