密码学从入门到放弃公钥密码

发表于 2022-05-20 分类于学习笔记阅读次数：

再续前缘，整理一下bibi师傅的笔记。

公钥密码部分。

公钥密码【Public-key cryptography，也称非对称密码学，是密码学的一种算法，它需要两个密钥，一个是公开密钥，另一个是私有密钥；一个用作加密，另一个则用作解密。使用其中一个密钥把明文加密后所得的密文，只能用相对应的另一个密钥才能解密得到原本的明文；甚至连最初用来加密的密钥也不能用作解密。由于加密和解密需要两个不同的密钥，故被称为非对称加密；不同于加密和解密都使用同一个密钥的对称加密。虽然两个密钥在数学上相关，但如果知道了其中一个，并不能凭此计算出另外一个来源请求；因此其中一个可以公开，称为公钥，任意向外发布；不公开的密钥为私钥，必须由用户自行严格秘密保管，绝不透过任何途径向任何人提供，也不会透露给被信任的要通信的另一方。

数论前置

欧拉函数

$\varphi(n)$表示为小于等于$n$的正整数中和$n$互质的数，对于质数来说，$\varphi(n)=1$。

欧几里得算法

求最大公约数的算法，又称辗转相除法。

# 递归版
def gcd(a, b):
    return a if not b else gcd(b, a % b)

# 迭代版
def gcd2(a, b):
    while b:
        a, b = b, a % b
    return a

裴蜀定理

𝑎𝑥+𝑏𝑦=𝑔𝑐𝑑(𝑎,𝑏)

对于任意的整数𝑎,b，都存在一对整数𝑥,y，使得$ax+by=gcd(a,b)$成立。

那么对于一个经典方程ax+by=1，有gcd(a,b)=1，即a,b一定互质。

扩展欧几里得算法

快速欧拉演算

求解不定方程
求解模的逆元
求解线性同余方程

从裴蜀定理的ax+by=m得出，若存在合法的x,y使得该不定方程有解，则其m必为gcd(a,b)的倍数。

a->e,b->(n)

而扩展欧几里得算法可以求出x,y的值。

乘法逆元

对于任意整数$a$和正整数$m$，取模运算就是求出$a$除以$m$的余数，通常表示为$a\,mod\,m$。

对于给定的整数$a$和模数$m$，如果存在一个整数$x$，使得$ax\,mod\,m$等于$1$，那么$x$就是$a$在模$m$下的乘法逆元。

注意，乘法逆元存在的前提是$a$和$m$互素（即$a$和$m$没有除$1$以外的公因子）。

例题

求47x+30y=1的整数解。

47=30*1+17 // y=1, x=1
30=17*1+13 //    
17=13*1+4 // 同上
13=4*3+1 // 同上

然后改写

17=47*1+30*(-1)
13=30*1+17*(-1)
4=17*1+13*(-1)
1=13+4*(-3)

倒回去

1=13+4*(-3)
1=13+[17*1+13*(-1)]*(-3)
1=17*(-3)+13*4
1= 17*(-3)+[30*1+17*(-1)]*4
1=30*4+17*(-7)
1=30*4+[47*1+30*(-1)]*(-7)
1=47*(-7)+30*11

def ext_euclid(a, b):
     if b == 0:
         return 1, 0, a
     else:
         x, y, q = ext_euclid(b, a % b) # q = gcd(a, b) = gcd(b, a%b)
         x, y = y, (x - (a // b) * y)
         return x, y, q

欧拉定理

中国剩余定理

《孙子算经》中有问：今有物不知其数，三三数之剩二，五五数之剩三，七七数之剩二，问物几何？在现代数论中我们把它写成解一元线性同余方程组。 \[ x\equiv2(mod\,3) \\ x\equiv3(mod\,5) \\ x\equiv2(mod\,7) \]

算法流程

计算模数之积：$N=n_1n_2n_3\cdot\cdot\cdot n_n$
对于第i个方程：
1. 计算$m_i=\frac{n}{n_i}$
2. 计算$m_i$对于$n_i$的逆元$m^{-1}_i$
3. 计算$c_i=m_im^{-1}_i$
方程得解：$x=\sum^{i=1}_{k}a_ic_i(mod\,n)$

def CRT(k, a, r):
    n = 1; ans = 0
    for i in range(1, k + 1):
        n = n * r[i]
    for i in range(1, k + 1):
        m = n // r[i]; b = y = 0
        exgcd(m, r[i], b, y) # b * m mod r[i] = 1
        ans = (ans + a[i] * m * b % n) % n
    return (ans % n + n) % n

举例求解

$n=3*5*7=105$
$m_1=\frac{n}{n_1}=35,m^{-1}_i=2,c_1=35*2=70$
依次得出$m_2=21,m^{-1}_2=1,c_2=21,m_3=15,m^{-1}_3=1,c_3=15$
故解为$x=a_1c_1+a_2c_2+a_3c_3\,(mod\,n)=233(mod\,105)=23$

RSA

原理

选两个大素数 $p$ 、 $q$ ,计算出模数 $N = p * q$ 。
再计算欧拉函数，$φ(N) = φ(p)φ(q) = (p−1)(q−1)$。
选择一个小于 $φ(N)$ 但大于 1 的整数 $e$，使 $e$ 和 $φ(N)$ 互质。
求得 $e$ 关于 $φ(N)$ 的模反元素，命名为 $d$ ，有 $ed\,mod\,\varphi(n)=1\,mod\,\varphi(n)$。

欧拉定理：e与n互质时，n的欧拉函数$\varphi(n)$使得$e^{φ(n)}=1\,mod\,n$，而n为质数，所以n的欧拉函数$\varphi(n)=n-1$，此时欧拉定理可写为$e^{n-1}=1\,mod\,n$，被称为费马小定理。

此时，$(N,e)$ 是公钥，发送给对方用来加密消息，$(N,d)$ 是私钥，自己留着用来解密消息。
消息加密：$m^e\,mod\,N=c$
消息解密：$c^d\,mod\,N=m$
在这个过程中，第三方窃听者只能获取到 $c,e,n$，无法解出明文 $m$。
其中，明文 $m$ 长度需小于模数 $n$。

加密过程

import gmpy
from Crypto.Util.number import *
from Crypto.PublicKey import RSA
from Crypto.Cipher import PKCS1_v1_5

msg = 'crypto here'
p = getPrime(128)
q = getPrime(128)
n = p*q
e = getPrime(64)
pubkey = RSA.construct((long(n), long(e)))
privatekey = RSA.construct((long(n), long(e), long(d), long(p), long(q)))
key = PKCS1_v1_5.new(pubkey)
enc = key.encrypt(msg).encode('base64')
key = PKCS1_v1_5.new(privatekey)
msg = key.decrypt(enc.decode('base64'), e)

一些工具

RSAtool

openssl

查看公钥文件

1	openssl rsa -pubin -in pubkey.pem -text -modulus

解密

1	rsautl -decrypt -inkey private.pem -in flag.enc -out flag

分解整数工具

rsa-wiener-attack

CTF-RSA-tool

直接模数分解

直接模数分解首当其冲的一个便是数学难题：分解大素数N。

暴力分解

当N的长度较小可直接分解【长度小于512bit。

例题

Jarvis OJ的一题Medium RSA，给了一个公钥和一个密文。

openssl rsa -in pubkey.pem -pubin -noout -text -modulus
Public-Key: (256 bit)
Modulus:
    00:c2:63:6a:e5:c3:d8:e4:3f:fb:97:ab:09:02:8f:
    1a:ac:6c:0b:f6:cd:3d:70:eb:ca:28:1b:ff:e9:7f:
    be:30:dd
Exponent: 65537 (0x10001)
Modulus=C2636AE5C3D8E43FFB97AB09028F1AAC6C0BF6CD3D70EBCA281BFFE97FBE30DD

N很小，可以直接分解，使用CTF-RSA-Tool。

python solve.py --verbose --private -N 87924348264132406875276140514499937145050893665602592992418171647042491658461 -e 65537
DEBUG: factor N: try past ctf primes
DEBUG: factor N: try Gimmicky Primes method
DEBUG: factor N: try Wiener's attack
DEBUG: Starting new HTTP connection (1): www.factordb.com:80
DEBUG: http://www.factordb.com:80 "GET /index.php?query=87924348264132406875276140514499937145050893665602592992418171647042491658461 HTTP/1.1" 200 1021
DEBUG: http://www.factordb.com:80 "GET /index.php?id=1100000000836631227 HTTP/1.1" 200 899
DEBUG: http://www.factordb.com:80 "GET /index.php?id=1100000000836631226 HTTP/1.1" 200 898
DEBUG: d = 0x1806799bd44ce649122b78b43060c786f8b77fb1593e0842da063ba0d8728bf1L
INFO:
p=275127860351348928173285174381581152299
q=319576316814478949870590164193048041239
d=10866948760844599168252082612378495977388271279679231539839049698621994994673

INFO: private key:
-----BEGIN RSA PRIVATE KEY-----
MIGqAgEAAiEAwmNq5cPY5D/7l6sJAo8arGwL9s09cOvKKBv/6X++MN0CAwEAAQIg
GAZ5m9RM5kkSK3i0MGDHhvi3f7FZPghC2gY7oNhyi/ECEQDO+7LPfhipjr7cNuPn
w7ArAhEA8Gwo6RyJIrnCNuI1YMCXFwIRAJulRkclqWIHx5pNZIAp9VUCEGjeJLIZ
ek+lSut5m+LJ3p0CEDRBEd7C622/wt1+58xOIfE=
-----END RSA PRIVATE KEY-----

然后解出flag。

import libnum
from Crypto.Util.number import long_to_bytes

n = 87924348264132406875276140514499937145050893665602592992418171647042491658461
d = 10866948760844599168252082612378495977388271279679231539839049698621994994673
c = open('flag.enc').read().encode('hex')
c = int(c, 16)
m = pow(c, d, n)
print long_to_bytes(m)
# ���&[�PCTF{256b_i5_m3dium}

PQ选择不当

N中P和Q选择存在的问题【过于接近/差距过大/光滑。

|p-q|很大：当p-q很大时，一定存在某一个参数较小，这里我们假设为p，那么我们可以通过穷举的方法对模数进行试除，从而分解模数，得到保密参数与明文信息。基本来说，不怎么可行。
费马分解和Pollard_rho分解
p-1光滑
p+1光滑【2017 SECCON very smooth
一些特定的N【在factordb上测试一下

Yafu分解

例题

[xman2019]xyf

1
2
3

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

公约数模数分解

如果在两个模数中使用了1个相同的素因子，那么可以使用求最大公约数的方法求出来

一般会给两个很难通过其他方法解出的模数

c1,e1,n1

c2,e2,n2

gcd(n1,n2)如果不是1的话，那么就可以分解n1和n2

共模攻击

两组及以上的RSA加密过程，而且其中两次的$m$和$n$都是相同的，但是$e$不同，那么就可以使用共模攻击。 \[ c_1=m^{e_1}\,mod\,N \\ c_2=m^{e_2}\,mod\,N \]

使用扩展的欧几里得算法求出$r$和$s$ \[ re_1+se_2=1\,mod\,N \\ c^r_1c^s_2=(m^{re_1})*(m^{se_2})mod\,N=m\,mod\,N \]

例题

[xman2019]xgm

import gmpy2
from Crypto.Util.number import long_to_bytes

e1 = 773
e2 = 839
n = 6266565720726907265997241358331585417095726146341989755538017122981360742813498401533594757088796536341941659691259323065631249
c1 = 3453520592723443935451151545245025864232388871721682326408915024349804062041976702364728660682912396903968193981131553111537349
c2 = 5672818026816293344070119332536629619457163570036305296869053532293105379690793386019065754465292867769521736414170803238309535

_, r, s = gmpy2.gcdext(e1, e2)

m = pow(c1, r, n) * pow(c2, s, n) % n
print(m)
i = 0
flag = ""
plain = str(m)
while i < len(plain):
    if plain[i] == '1':
        flag += chr(int(plain[i:i + 3]))
        i += 3
    else:
        flag += chr(int(plain[i:i + 2]))
        i += 2
print(flag)
print(long_to_bytes(m))

小指数明文爆破

\[ c = m^e\,mod\,N \]

如果$e$很小，比如$e=3$，那么如果明文也很小的情况下可能会出现这种情况：$m^e<n$

此时直接对$c$开$e$次根号就可以得到$m$。

还有一种一般一点的情况：

$kn<m^3<(k+1)n$

就是说$m^e$虽然大于$n$了但是没有超出太多

爆破$k$

例题

JarvisOJ，crypto，[xman2019]xbk

import gmpy2

e = 3
# 读入 n, 密文
n= 22885480907469109159947272333565375109310485067211461543881386718201442106967914852474989176175269612229966461160065872310916096148216253429849921988412342732706875998100337754561586600637594798877898552625378551427864501926224989873772743227733285336042475675299391051376624685754547818835551263597996620383338263448888107691240136257201191331617560711786674975909597833383395574686942099700631002290836152972352041024137872983284691831292216787307841877839674258086005814225532597955826353796634417780156185485054141684249037538570742860026295194559710972266059844824388916869414355952432189722465103299013237588737
c= 15685364647213619014219110070569189770745535885901269792039052046431067708991036961644224230125219358149236447900927116989931929305133870392430610563331490276096858863490412102016758082433435355613099047001069687409209484751075897343335693872741

print 'n=', n
print 'c=', c

print '[+]Detecting m...'
result = gmpy2.iroot(c, 3)

import gmpy2
from Crypto.Util.number import long_to_bytes

n = 114976915747243387792157708464120735018971336213935438953074748276198282761939060395482051056351068439137722626185590043024556656813730840050547350912425438364703854627760482842307943026011880815011654341047422453012558617703411700393668892701036222135444420377515575624398723436532681305293727164639582093389
c = 5828813410620741112500628876643872258919868379601617907887884191584237969605489971465692568848339200057188383649365078832766143513766368216471491824042974016773526107276856706832404477882581400769791378958901067683158857990261489285951805740071223765359992165262854641069674603160977034446644199945940251030
e = 3

i = 0
while 1:
    if (gmpy2.iroot(c + i * n, 3)[1] == 1):
        print(long_to_bytes(gmpy2.iroot(c + i * n, 3)[0]))
        break
    i = i + 1

1
2
3

e = 3
n = 18970053728616609366458286067731288749022264959158403758357985915393383117963693827568809925770679353765624810804904382278845526498981422346319417938434861558291366738542079165169736232558687821709937346503480756281489775859439254614472425017554051177725143068122185961552670646275229009531528678548251873421076691650827507829859299300272683223959267661288601619845954466365134077547699819734465321345758416957265682175864227273506250707311775797983409090702086309946790711995796789417222274776215167450093735639202974148778183667502150202265175471213833685988445568819612085268917780718945472573765365588163945754761
c = 150409620528139732054476072280993764527079006992643377862720337847060335153837950368208902491767027770946661

选择密文攻击

RSA parity oracle

假设目前存在一个 Oracle，它会对一个给定的密文进行解密，并且会检查解密的明文的奇偶性，并根据奇偶性返回相应的值，比如 1 表示奇数，0 表示偶数。那么给定一个加密后的密文，我们只需要 log(N) 次就可以知道这个密文对应的明文消息。

原理

Step 1

\[ C=P^emod\,N \]

如果我们给服务器发送$2^eC$，那么由于$2^eC=(2P)^e\,mod\,N$，服务器会计算$(2^eC)^d\,mod\,N=2^{ed}C^d\,mod\,N$得到$2P\,mod\,N$。

此处2P是偶数，其幂次也是偶数，而N是奇数，因为是两个素数相乘得到。

如果服务器返回奇数，则说明2P>N，因为偶数减去奇数为奇数。由2P>N，又因为P<N，得$\frac{N}{2}<P<N$。

如果服务器返回偶数，则说明2P<N，得$0<P<\frac{N}{2}$。

Step 2

假设第一步返回奇数，$\frac{N}{2}<P<N$。

那么继续给服务器发送$2^{2e}C$，即$4^eC$

https://dawn-whisper.hack.best/2020/10/10/RSA_Parity_Oracle/

Wiener’s Attack

在$e$过大或过小的情况下，可使用算法利用$e$快速推断出$d$的值。

与低加密指数相同，低解密指数可以加快解密的过程，但是也带来了安全问题。

如果满足$d<\frac{1}{3}n^{\frac{1}{4}}$，那么一种基于连分数【一个数论当中的问题】的特殊攻击类型就可以危害 RSA 的安全。

此时需要满足：$q<p<2q$，则可以在多项式时间中分解 $n$，思路如下。 \[ n=pq \\ \varphi(n)=(p-1)(q-1)=pq-(p+q)+1=n-(p+q)+1 \] 由于$n$很大，因此$\varphi(n)\approx n$，而$ed\equiv1\,mod\,\varphi(n)$得$ed-1=k\varphi(n)$，两边同除$d\varphi(n)$得$\frac{e}{\varphi(n)}-\frac{k}{d}=\frac{1}{d\varphi(n)}$。

$\varphi(n)$很大，且近似$n$，故等式右边近似0，得出$\frac{e}{n}$略大于$\frac{k}{d}$。

而在RSA中，对于窃听者而言，$e$和$n$是公开的，那么对于$\frac{k}{d}$，计算出$\frac{e}{n}$的每个渐进分数，便可精确覆盖$\frac{k}{d}$。【论文的结论，不多赘述】

例子

设公钥(N,e)=(90581,17993)。

先求$\frac{e}{n}$的渐进分数。 \[ \frac{e}{n}=\frac{17993}{90581} \\=\frac{1}{\frac{90581}{17993}}=\frac{1}{5+\frac{616}{17993}} \\=\frac{1}{5+\frac{1}{\frac{17993}{616}}}=\frac{1}{5+\frac{1}{29+\frac{129}{616}}}... \]

故有$\frac{k}{d}=0,\frac{1}{5},\frac{29}{146}...$

假设$\frac{29}{146}$成立，则$k=29$，$d=146$，代入$ed-1=k\varphi(n)$，得出$\varphi(n)$的值，又因$\varphi(n)=n-(p+q)+1$，故得到p+q和pq的值。

由韦达定理可解。

例题

1
2
3

n = 12238605063252292170613110607692779326628090745751955692266649177882959231822580682548279800443278979485092243645806337103841086023159482786712759291169541633901936290854044069486201989034158882661270017305064348254800318759062921744741432214818915527537124001063995865927527037625277330117588414586505635959411443039463168463608235165929831344586283875119363703480280602514451713723663297066810128769907278246434745483846869482536367912810637275405943566734099622063142293421936734750356828712268385319217225803602442033960930413469179550331907541244416573641309943913383658451409219852933526106735587605884499707827
e = 11850552481503020257392808424743510851763548184936536180317707155841959788151862976445957810691568475609821000653594584717037528429828330763571556164988619635320288125983463358648887090031957900011546300841211712664477474767941406651977784177969001025954167441377912326806132232375497798238928464025466905201977180541053129691501120197010080001677260814313906843670652972019631997467352264392296894192998971542816081534808106792758008676039929763345402657578681818891775091140555977382868531202964486261123748663752490909455324860302967636149379567988941803701512680099398021640317868259975961261408500449965277690517
c = 9472193174575536616954091686751964873836697237500198884451530469300324470671555310791335185133679697207007374620225900775502162690848135615431624557389304657410880981454777737587420426091879654002644281066474715074536611611252677882396384453641127487515845176069574754606670518031472235144795376526854484442135299818868525539923568705203042265537204111153151119105287648912908771710419648445826883069030285651763726003413418764301988228077415599665616637501056116290476861280240577145515875430665394216054222788697052979429015400411487342877096677666406389711074591330476335174211990429870900468249946600544116793793

求解。

import gmpy2


def transform(x,y):       #使用辗转相处将分数 x/y 转为连分数的形式
    res=[]
    while y:
        res.append(x//y)
        x,y=y,x%y
    return res
    
def continued_fraction(sub_res):
    numerator,denominator=1,0
    for i in sub_res[::-1]:      #从sublist的后面往前循环
        denominator,numerator=numerator,i*numerator+denominator
    return denominator,numerator   #得到渐进分数的分母和分子，并返回

    
#求解每个渐进分数def sub_fraction(x,y):
    res=transform(x,y)
    res=list(map(continued_fraction,(res[0:i] for i in range(1,len(res)))))  #将连分数的结果逐一截取以求渐进分数
    return res

#以上是获得e/n的连分数

def get_pq(a,b,c):      #由p+q和pq的值通过维达定理来求解p和q
    par=gmpy2.isqrt(b*b-4*a*c)   #由上述可得，开根号一定是整数，因为有解
    x1,x2=(-b+par)//(2*a),(-b-par)//(2*a)
    return x1,x2

def wienerAttack(e,n):
    for (d,k) in sub_fraction(e,n):  #用一个for循环来注意试探e/n的连续函数的渐进分数，直到找到一个满足条件的渐进分数
        if k==0:                     #可能会出现连分数的第一个为0的情况，排除
            continue
        if (e*d-1)%k!=0:             #ed=1 (\pmod φ(n)) 因此如果找到了d的话，(ed-1)会整除φ(n),也就是存在k使得(e*d-1)//k=φ(n)
            continue
        
        phi=(e*d-1)//k               #这个结果就是 φ(n)
        px,qy=get_pq(1,n-phi+1,n)
        if px*qy==n:
            p,q=abs(int(px)),abs(int(qy))     #可能会得到两个负数，负负得正未尝不会出现
            d=gmpy2.invert(e,(p-1)*(q-1))     #求ed=1 (\pmod  φ(n))的结果，也就是e关于 φ(n)的乘法逆元d
            return d
    print("该方法不适用")
    
    
e = 14058695417015334071588010346586749790539913287499707802938898719199384604316115908373997739604466972535533733290829894940306314501336291780396644520926473
n = 33608051123287760315508423639768587307044110783252538766412788814888567164438282747809126528707329215122915093543085008547092423658991866313471837522758159
d = wienerAttack(e,n)
print("d=",d)

广播攻击

如果相同的信息被不同的公钥加密的了，并且如果使用的$e$较小，就可以进行广播攻击。

准确的条件：$m.bit_length*e < c.bit_length $。

$m$和$e$相同，由于不同的$n$计算出不同的$c$，故有： \[ c_1=m^e\,mod\,n_1 \\ c_2=m^e\,mod\,n_2 \\ c_3=m^e\,mod\,n_3 \\\cdot\cdot\cdot\\ c_n=m^e\,mod\,n_n \] 在$n_i$互素时，通过中国剩余定理，得到$c \equiv m^e \pmod {n_1n_2n_3\cdot\cdot\cdot n_n}$。

若不互素，可通过欧几里得算法求解$pq$。

当$c < n_1n_2n_3\cdot\cdot\cdot n_n$时，上面等式成立，故此时开e次方即可得解。

sudo apt install libgmp-dev
sudo apt install libmpfr-dev
sudo apt install libmpc-dev
pip install sympy gmpy2

from Crypto.Util.number import long_to_bytes
from gmpy2 import iroot
from sympy.ntheory.modular import crt

e = 9
N = [142782424368849674771976671955176187834932417027468006479038058385550042422280158726561712259205616626939123504489410624745195777853423961104590708231562726165590769610040722589287393102301338152085670464005026301781192671834390892019478189768725018303217559795377795540494239283891894830166363576205812991157,153610425077816156109768509904751446801233412970601397035720458311275245730833227428213917577405780162151444202393431444812010569489900435979730559895340377469612234558042643742219128033827948585534761030527275423811282367831985007507137144308704413007806012914286105842311420933479771294576841956749281552971,152540067782701001222493009941492423063369171831039847414320547494725020441901272486665728360741395415762864872737675660423920609681185809510355937534756399208661762715484879562585724584849261266873624875852300611683382543315580370484972470694466195837255994159609193239840228218925381488410059939975556977947,125842716702134814646356078531900645012495638692517778270527426844383063904041812273637776798591687732598509470005151551320457132061693618473039437320011446697406190781306264437609046721508738109650829547010385875425097336266103994639126319889016342284747700714199556143378526590058467791687837422897022829661,116144389285266462769913139639175922392318396923181100785008570884082681963637784423143843845816350379438789947802939701820129805341796427821894273985551331666719808355412080909245720551238149511778060242720419584504473490216670437024863860559347959698828131475160058721701582089480924088773887932997353631767,127833907448946785858374094953899556339175475846831397383049660262333005992005484987913355932559627279178940862787593749842796469355336182379062826441222705075178971785791223706944120681105575965622931327112817747065200324610697178273898956820957640413744954233327851461318200323486469677469950386824833536523,130561613227079478921314550968562766645507834694262831586725464124109153306162445639759476845681271537955934718244296904503168256991962908095007040044300188572466395275317838178325500238288302672390013747102961340256309124310478931896245221622317302428447389760864327859640573452084295225059466376349115703119,115953389401040751013569404909249958538962411171147823610874077094621794755967854844224923689925397631692572916641171075740839099217316101334941033937183815345038898177087515909675028366437302462022970987947264115373697445950951595479758872029099661065186221250394358255523574834723958546450323357472451930993,143437107845384843564651522639125300763388830136500260725097766445883003928355325003575359566631064630487365774344508496878731109174874449170057678821440711511966073934025028100604234445470976333825866939923998344367645612128590820812489407412175198698290167077116185959180877334222693344630253253476594907313]
C = [85033868418784308573673709960700777350314426427677627319697346811123742342359072170220428874952996988431950989321281905284522596263957356289624365171732095210045916218066135140320107686084053271623461104022705353814233772164502775939590711842361956121603943483040254727995655776263673058788416722141673409688,66065963470666895005407449599703926269325406456711861190876894466341571726360462706664546294453572319565476664348345756905411939632955966517708138047546806602828064213238537646393524578984547577761559965654539771172357089802682793169968961304179886652390277814477825753096636750388350662980872556701402397564,116011740820520887443111656288411611070614127688662643257265381793048354928820176624229624692124188995846076431510548507016903260774215950803926107831505634778278712070141663189086436127990584944132764896694777031370995058271038329228336417590284517922855284619653301817355115583540545182119702335431334401666,97640420284096094887471273365295984332267897927392169402918423863919914002451127544715668846623138003564829254309568918651163254043205129883843425179687841236818720463784828905460885026290909768599562386370732119591181513319548915478512030197629196018254041500662654260834562708620760373487652389789200792120,8112507653841374573057048967617108909055624101437903775740427861003476480616929517639719198652146909660899632120639789106782550275648578142883715280547602249589837441805676364041484345030575130408744621981440093280624046635769338568542048839419939250444929802135605724150484414516536378791500915047844188300,36792148360808115566234645242678223867680969786675055638670907933041180936164293809961667801099516457636164692292891528415720085345494773373966277807505798679784807614784581861287048096977968620964436947452527540958289441390882589051225367658014709290392321808926567572528170531844664734909469690750971883323,53043093283305492238903255767698153246673671181809989362223466090875767705978690531154079519999671834688647277179370374802495005937892824566602423646978168777735383632928274082669949750078161820002768640908750005814934158829006019656592134357897586040866207754535586785064545866404380204728594863102313407789,88499407133762624445946519155722583633934260410706930537441122463087556094734626189377091740335667052378955691250910459790202385799502439716173363179773811920751410726795431402796346647688144853156900427797933862087074385441977254140336390678022955770879265490567987868532251217565094093318626424653599450992,138337520305048557335599940473834485492131424901034295018189264168040969172072024612859307499682986987325414798210700710891033749119834960687318156171051379643844580970963540418974136891389303624057726575516576726845229494107327508855516437230240365759885913142671816868762838801720492804671259709458388192984]

resultant, mod = crt(N, C)
value, is_perfect = iroot(resultant, e)
print(long_to_bytes(value))