一道题入门RSA

接触CTF不久，还处于杂食阶段，所以自己还没有什么系统的学习计划，各类题型都看一点。说到crypto肯定离不开rsa，正好久闻RSA加密的大名，借机了解一下这个“地球上最重要的加密算法”

0x00 RSA加密过程

加密算法可以分为两类：对称加密和非对称加密。对称加密弱点在于双方使用相同的密钥进行加密解密。密钥要么随密文传递，要么线下约定。一旦被攻击者截获，密钥不再保密。而非对称加密工作原理是公钥加密私钥解密，发送方只需要知道对外界公开的公钥即可进行加密，接收方持有私钥，无需也不能参与传输。
RSA就是非对称加密的代表之一，其详细过程如下：
~~（让我们请出不发消息会死星人Alice和Bob）🎉~~
假设Alice是接收方，Bob是发送方。
第一步，Alice随机选取两大质数p、q，然后相乘得到n。p、q越大，密钥越难被破解。
第二步，计算n的欧拉函数φ(n)，由欧拉函数的结论可知，φ(n)=(p-1)(q-1)
第三步，随机选择一个整数e满足1< e < φ(n)，且e与φ(n) 互质，一般选择65537
到此为止，公钥选取完成:(e,n)
接下来计算私钥。
第四步，计算e对于φ(n)的模反元素d。由 ed ≡ 1 (mod φ(n)) ，得 ex + φ(n)y = 1，借助拓展欧几里得定理，计算出x、y中的正整数，记为d
私钥即(d,n)

0x01 原题

from gmpy2 import *
from Crypto.Util.number import *
from flag import flag
q = getPrime(1024)
p = getPrime(1024)
n = p * q
e = 0x10001

m = bytes_to_long(flag)
c = pow(m , e , n)
print('c =' , c)
print('p =' , p)
print('q =' , q)
print('n =' , n)
print('e =' , e)


#c = 12786994906832886031173089454539830225421640443805160963440942546071910322282773910135388020414967368794768319321460372875327006020157548651622969466323905189761834455201291838045352561790791600881627927594863932384116760236609096504346833060291203939690475993692410973499329433726175351882818053841075210942250478835641657575946226612389154039920962506062857726362447590070697348315291411570674334126096132112365825105842643843896421848410966564321518660727994853036555116782763422065173850238826345797198901647320210828033061322523971939726188821545177029535860881611210887039411052848607563035583276075332653567834
#p = 161719691876167304386300539654699854745688262478039691942271426308613132466937889105173933022986654040443219708318126579048996288583272346602042650222520127626611975688909019632479930508343350314542889627461529623000987307169157443265879212155437165660477850241678385286601587538517091605374764970915451201471
#q = 131679150542057883837006988923642169851011066771905140540444762603374903776910595387305441746623070810587630852182725227845916400198693359271062585498062084740896090668288333576457754165324164735966791029516030696195703650691726650990903496820364700241229117883279657833543807874786274886417501405960125022153
#n = 21295111652177049852547386222656846645616549922902112221240647622752994625687294739828756977846793220378085163155773051922086862363248151399852421844018730199066331944608000906761112010951655369036878807145188296884981895884278542857120225505310980291226351653588799242142355376939447934804833830853036785704513557039806761305316841740131204576974408869765714675230132247412774215945663807730855436503625577606009921411947891570324777735323489304604987902364932089976811865007609745513534209603256719511305317200247134396733168695387708420206468160279271453425776388025425790010391137010735121696446552257334341187063
#e = 65537

0x02 题解

from Crypto.Util.number import *
c = 12786994906832886031173089454539830225421640443805160963440942546071910322282773910135388020414967368794768319321460372875327006020157548651622969466323905189761834455201291838045352561790791600881627927594863932384116760236609096504346833060291203939690475993692410973499329433726175351882818053841075210942250478835641657575946226612389154039920962506062857726362447590070697348315291411570674334126096132112365825105842643843896421848410966564321518660727994853036555116782763422065173850238826345797198901647320210828033061322523971939726188821545177029535860881611210887039411052848607563035583276075332653567834
p = 161719691876167304386300539654699854745688262478039691942271426308613132466937889105173933022986654040443219708318126579048996288583272346602042650222520127626611975688909019632479930508343350314542889627461529623000987307169157443265879212155437165660477850241678385286601587538517091605374764970915451201471
q = 131679150542057883837006988923642169851011066771905140540444762603374903776910595387305441746623070810587630852182725227845916400198693359271062585498062084740896090668288333576457754165324164735966791029516030696195703650691726650990903496820364700241229117883279657833543807874786274886417501405960125022153
n = 21295111652177049852547386222656846645616549922902112221240647622752994625687294739828756977846793220378085163155773051922086862363248151399852421844018730199066331944608000906761112010951655369036878807145188296884981895884278542857120225505310980291226351653588799242142355376939447934804833830853036785704513557039806761305316841740131204576974408869765714675230132247412774215945663807730855436503625577606009921411947891570324777735323489304604987902364932089976811865007609745513534209603256719511305317200247134396733168695387708420206468160279271453425776388025425790010391137010735121696446552257334341187063
e = 65537

# n = p*q => phi n = (p-1)*(q-1)
fn = (p-1)*(q-1)
# ed ≡ 1(mod fn) => e*x+fn*y=1 求模拟元 x,y
def ext_Euclid(n, m):
    if (m == 0):
        return 1, 0
    else:
        x, y = ext_Euclid(m, n%m)
        x, y = y, (x -(n//m)*y)
        return x, y
x,y = ext_Euclid(e,fn)
d=(x+fn)%fn
m=pow(c,d,n)
print(long_to_bytes(m))