从零开始学RSA：低加密指数攻击2

1.低加密指数攻击

加密指数指的是e，因为e是可以随机选取的，当e很小时就会被直接破解掉。

当e=3，而且明文也很小，导致明文的三次方仍然小于n，那么通过直接对密文3次开放，即可得到明文。

C=me mod n

如果e=3，且me<n，那么

me mod n= me ，即C=me

m=3√c

如果e=3，且me>n，那么设k，有：

c= me +kn

爆破k，如果c−kn能开三次根式，那么可以直接得到明文。

┌──(holyeyes㉿kali2023)-[~/Misc/RSA/extremelyhardRSA]

└─$ openssl rsa -pubin -text -modulus -in pubkey.pem

Public-Key: (4096 bit)

Modulus:

    00:b0:be:e5:e3:e9:e5:a7:e8:d0:0b:49:33:55:c6:

    18:fc:8c:7d:7d:03:b8:2e:40:99:51:c1:82:f3:98:

    de:e3:10:45:80:e7:ba:70:d3:83:ae:53:11:47:56:

    56:e8:a9:64:d3:80:cb:15:7f:48:c9:51:ad:fa:65:

    db:0b:12:2c:a4:0e:42:fa:70:91:89:b7:19:a4:f0:

    d7:46:e2:f6:06:9b:af:11:ce:bd:65:0f:14:b9:3c:

    97:73:52:fd:13:b1:ee:a6:d6:e1:da:77:55:02:ab:

    ff:89:d3:a8:b3:61:5f:d0:db:49:b8:8a:97:6b:c2:

    05:68:48:92:84:e1:81:f6:f1:1e:27:08:91:c8:ef:

    80:01:7b:ad:23:8e:36:30:39:a4:58:47:0f:17:49:

    10:1b:c2:99:49:d3:a4:f4:03:8d:46:39:38:85:15:

    79:c7:52:5a:69:98:4f:15:b5:66:7f:34:20:9b:70:

    eb:26:11:36:94:7f:a1:23:e5:49:df:ff:00:60:18:

    83:af:d9:36:fe:41:1e:00:6e:4e:93:d1:a0:0b:0f:

    ea:54:1b:bf:c8:c5:18:6c:b6:22:05:03:a9:4b:24:

    13:11:0d:64:0c:77:ea:54:ba:32:20:fc:8f:4c:c6:

    ce:77:15:1e:29:b3:e0:65:78:c4:78:bd:1b:eb:e0:

    45:89:ef:9a:19:7f:6f:80:6d:b8:b3:ec:d8:26:ca:

    d2:4f:53:24:cc:de:c6:e8:fe:ad:2c:21:50:06:86:

    02:c8:dc:dc:59:40:2c:ca:c9:42:4b:79:00:48:cc:

    dd:93:27:06:80:95:ef:a0:10:b7:f1:96:c7:4b:a8:

    c3:7b:12:8f:9e:14:11:75:16:33:f7:8b:7b:9e:56:

    f7:1f:77:a1:b4:da:ad:3f:c5:4b:5e:7e:f9:35:d9:

    a7:2f:b1:76:75:97:65:52:2b:4b:bc:02:e3:14:d5:

    c0:6b:64:d5:05:4b:7b:09:6c:60:12:36:e6:cc:f4:

    5b:5e:61:1c:80:5d:33:5d:ba:b0:c3:5d:22:6c:c2:

    08:d8:ce:47:36:ba:39:a0:35:44:26:fa:e0:06:c7:

    fe:52:d5:26:7d:cf:b9:c3:88:4f:51:fd:df:df:4a:

    97:94:bc:fe:0e:15:57:11:37:49:e6:c8:ef:42:1d:

    ba:26:3a:ff:68:73:9c:e0:0e:d8:0f:d0:02:2e:f9:

    2d:34:88:f7:6d:eb:62:bd:ef:7b:ea:60:26:f2:2a:

    1d:25:aa:2a:92:d1:24:41:4a:80:21:fe:0c:17:4b:

    98:03:e6:bb:5f:ad:75:e1:86:a9:46:a1:72:80:77:

    0f:12:43:f4:38:74:46:cc:ce:b2:22:2a:96:5c:c3:

    0b:39:29

Exponent: 3 (0x3)

Modulus=B0BEE5E3E9E5A7E8D00B493355C618FC8C7D7D03B82E409951C182F398DEE3104580E7BA70D383AE5311475656E8A964D380CB157F48C951ADFA65DB0B122CA40E42FA709189B719A4F0D746E2F6069BAF11CEBD650F14B93C977352FD13B1EEA6D6E1DA775502ABFF89D3A8B3615FD0DB49B88A976BC20568489284E181F6F11E270891C8EF80017BAD238E363039A458470F1749101BC29949D3A4F4038D463938851579C7525A69984F15B5667F34209B70EB261136947FA123E549DFFF00601883AFD936FE411E006E4E93D1A00B0FEA541BBFC8C5186CB6220503A94B2413110D640C77EA54BA3220FC8F4CC6CE77151E29B3E06578C478BD1BEBE04589EF9A197F6F806DB8B3ECD826CAD24F5324CCDEC6E8FEAD2C2150068602C8DCDC59402CCAC9424B790048CCDD9327068095EFA010B7F196C74BA8C37B128F9E1411751633F78B7B9E56F71F77A1B4DAAD3FC54B5E7EF935D9A72FB176759765522B4BBC02E314D5C06B64D5054B7B096C601236E6CCF45B5E611C805D335DBAB0C35D226CC208D8CE4736BA39A0354426FAE006C7FE52D5267DCFB9C3884F51FDDFDF4A9794BCFE0E1557113749E6C8EF421DBA263AFF68739CE00ED80FD0022EF92D3488F76DEB62BDEF7BEA6026F22A1D25AA2A92D124414A8021FE0C174B9803E6BB5FAD75E186A946A17280770F1243F4387446CCCEB2222A965CC30B3929

writing RSA key

-----BEGIN PUBLIC KEY-----

MIICIDANBgkqhkiG9w0BAQEFAAOCAg0AMIICCAKCAgEAsL7l4+nlp+jQC0kzVcYY

/Ix9fQO4LkCZUcGC85je4xBFgOe6cNODrlMRR1ZW6Klk04DLFX9IyVGt+mXbCxIs

pA5C+nCRibcZpPDXRuL2BpuvEc69ZQ8UuTyXc1L9E7Huptbh2ndVAqv/idOos2Ff

0NtJuIqXa8IFaEiShOGB9vEeJwiRyO+AAXutI442MDmkWEcPF0kQG8KZSdOk9AON

Rjk4hRV5x1JaaZhPFbVmfzQgm3DrJhE2lH+hI+VJ3/8AYBiDr9k2/kEeAG5Ok9Gg

Cw/qVBu/yMUYbLYiBQOpSyQTEQ1kDHfqVLoyIPyPTMbOdxUeKbPgZXjEeL0b6+BF

ie+aGX9vgG24s+zYJsrST1MkzN7G6P6tLCFQBoYCyNzcWUAsyslCS3kASMzdkycG

gJXvoBC38ZbHS6jDexKPnhQRdRYz94t7nlb3H3ehtNqtP8VLXn75NdmnL7F2dZdl

UitLvALjFNXAa2TVBUt7CWxgEjbmzPRbXmEcgF0zXbqww10ibMII2M5HNro5oDVE

JvrgBsf+UtUmfc+5w4hPUf3f30qXlLz+DhVXETdJ5sjvQh26Jjr/aHOc4A7YD9AC

LvktNIj3betive976mAm8iodJaoqktEkQUqAIf4MF0uYA+a7X6114YapRqFygHcP

EkP0OHRGzM6yIiqWXMMLOSkCAQM=

-----END PUBLIC KEY-----

                                                                             

┌──(holyeyes㉿kali2023)-[~/Misc/RSA/extremelyhardRSA]

└─$

#!/usr/bin/python

#coding:utf-8

#小明文攻击  

#适用情况:e较小,一般为3

#公钥e很小，明文m也不大的话，于是m^e=k*n+m 中的的k值很小甚至为0，爆破k或直接开三次方即可。



import gmpy2,binascii,libnum,time

n=0xB0BEE5E3E9E5A7E8D00B493355C618FC8C7D7D03B82E409951C182F398DEE3104580E7BA70D383AE5311475656E8A964D380CB157F48C951ADFA65DB0B122CA40E42FA709189B719A4F0D746E2F6069BAF11CEBD650F14B93C977352FD13B1EEA6D6E1DA775502ABFF89D3A8B3615FD0DB49B88A976BC20568489284E181F6F11E270891C8EF80017BAD238E363039A458470F1749101BC29949D3A4F4038D463938851579C7525A69984F15B5667F34209B70EB261136947FA123E549DFFF00601883AFD936FE411E006E4E93D1A00B0FEA541BBFC8C5186CB6220503A94B2413110D640C77EA54BA3220FC8F4CC6CE77151E29B3E06578C478BD1BEBE04589EF9A197F6F806DB8B3ECD826CAD24F5324CCDEC6E8FEAD2C2150068602C8DCDC59402CCAC9424B790048CCDD9327068095EFA010B7F196C74BA8C37B128F9E1411751633F78B7B9E56F71F77A1B4DAAD3FC54B5E7EF935D9A72FB176759765522B4BBC02E314D5C06B64D5054B7B096C601236E6CCF45B5E611C805D335DBAB0C35D226CC208D8CE4736BA39A0354426FAE006C7FE52D5267DCFB9C3884F51FDDFDF4A9794BCFE0E1557113749E6C8EF421DBA263AFF68739CE00ED80FD0022EF92D3488F76DEB62BDEF7BEA6026F22A1D25AA2A92D124414A8021FE0C174B9803E6BB5FAD75E186A946A17280770F1243F4387446CCCEB2222A965CC30B3929

e=3

res=0   #res即k

c=int(open('flag.enc','rb').read().encode('hex'),16)

print time.asctime()

for i in xrange(200000000):

    if gmpy2.iroot(c+n*i,3)[1]==1:

        res=gmpy2.iroot(c+n*i,3)[0]

        print i,res

        print libnum.n2s(res)

        print time.asctime()

        break

#PCTF{Sm4ll_3xpon3nt_i5_W3ak}

2 低加密指数分解攻击

01 e=2把c开平方求解

已知:

e=2

c=9217979941366220275377875095861710925207028551771520610387238734819759256223080175603032167658086669886661302962985046348865181740591251321966682848536331583243529

求明文m?

#!/usr/bin/python

#coding:utf-8

#@Author:醉清风



import gmpy2

import libnum

c = 9217979941366220275377875095861710925207028551771520610387238734819759256223080175603032167658086669886661302962985046348865181740591251321966682848536331583243529

m = gmpy2.isqrt(c)

m = int(m)

m_text = libnum.n2s(m)

print(m_text)

#flag1{Th1s_i5_wHat_You_ne3d_FirsT}

02 e=2 Rabin加密中的N可被分解

Rabin加密是RSA的衍生算法，可以百度或阅读：

Rabin_cryptosystem

e=2是Rabin加密典型特征，但并不是所有的RSA在e=2时都是Rabin加密。

Rabin解密的Python实现:

def rabin_decrypt(c, p, q, e=2):  

    n = p * q  

    mp = pow(c, (p + 1) / 4, p)  

    mq = pow(c, (q + 1) / 4, q)  

    yp = gmpy2.invert(p, q)  

    yq = gmpy2.invert(q, p)  

    r = (yp * p * mq + yq * q * mp) % n  

    rr = n - r  

    s = (yp * p * mq - yq * q * mp) % n  

    ss = n - s  

    return (r, rr, s, ss)

题目: 02-Jarvis OJ -Crypto-Hard RSA

确实如题目描述的一般，出题人做手脚了，按照之前做MediumRSA的步骤做完全做不出来，而且求d的时候就会报错找不到e的模反数:

ValueError: no invmod for given @a and @n

所以要多积累一些题型，这里就是考察的e=2时，Rabin加密中的N可被分解。

首先通过openssl提取公钥的信息：

┌──(holyeyes㉿kali2023)-[~/Misc/RSA/hardRSA]

└─$ openssl rsa -pubin -in pubkey.pem -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: 2 (0x2)

Modulus=C2636AE5C3D8E43FFB97AB09028F1AAC6C0BF6CD3D70EBCA281BFFE97FBE30DD

writing RSA key

-----BEGIN PUBLIC KEY-----

MDowDQYJKoZIhvcNAQEBBQADKQAwJgIhAMJjauXD2OQ/+5erCQKPGqxsC/bNPXDr

yigb/+l/vjDdAgEC

-----END PUBLIC KEY-----

                                                                             

┌──(holyeyes㉿kali2023)-[~/Misc/RSA/hardRSA]

└─$

发现e为2，结合题目描述，应为rabin算法。

分解n得到p,q：

E:\MISC\RSA\yafu-1.34>yafu-x64.exe "factor(87924348264132406875276140514499937145050893665602592992418171647042491658461)"




fac: factoring 87924348264132406875276140514499937145050893665602592992418171647042491658461

fac: using pretesting plan: normal

fac: no tune info: using qs/gnfs crossover of 95 digits

div: primes less than 10000

fmt: 1000000 iterations

rho: x^2 + 3, starting 1000 iterations on C77

rho: x^2 + 2, starting 1000 iterations on C77

rho: x^2 + 1, starting 1000 iterations on C77

pm1: starting B1 = 150K, B2 = gmp-ecm default on C77

ecm: 30/30 curves on C77, B1=2K, B2=gmp-ecm default

ecm: 74/74 curves on C77, B1=11K, B2=gmp-ecm default

ecm: 149/149 curves on C77, B1=50K, B2=gmp-ecm default, ETA: 0 sec



starting SIQS on c77: 87924348264132406875276140514499937145050893665602592992418171647042491658461



==== sieving in progress (1 thread):   36224 relations needed ====

====           Press ctrl-c to abort and save state           ====

34307 rels found: 17318 full + 16989 from 186791 partial, (2492.12 rels/sec)



SIQS elapsed time = 86.1623 seconds.

Total factoring time = 99.2821 seconds




***factors found***



P39 = 275127860351348928173285174381581152299

P39 = 319576316814478949870590164193048041239



ans = 1

#!/usr/bin/python

#coding:utf-8



import gmpy2

import libnum



e = 2

n = 87924348264132406875276140514499937145050893665602592992418171647042491658461

p = 275127860351348928173285174381581152299

q = 319576316814478949870590164193048041239

c=int(open('./flag.enc','rb').read().encode('hex'),16)



mp=pow(c,(p+1)/4,p)

mq=pow(c,(q+1)/4,q)

yp=gmpy2.invert(p,q)

yq=gmpy2.invert(q,p)

r=(yp*p*mq+yq*q*mp)%n

rr=n-r

s=(yp*p*mq-yq*q*mp)%n

ss=n-s

print libnum.n2s(r)

print libnum.n2s(rr)

print libnum.n2s(s)

print libnum.n2s(ss)



 #PCTF{sp3ci4l_rsa}

记住这是模板，以后有类似的题目直接拿来用就好，对了一般读取文件获得变量c的值都是这样表示的，这会使代码看上去更简洁。

适用情况：e较小，一般为3。

03 e=3 小明文攻击

公钥e很小，明文m也不大的话，于是m^e=k*n+m 中的的k值很小甚至为0，爆破k或直接开三次方即可。

攻击原理：假设用户使用的密钥 e=3。考虑到加密关系满足：

C ≡ m^3 \,mod \,\, N \\

那么：

m^3 =C + k * N \\ m = \sqrt[3]{C + k * N}\\攻击者可以从小到大枚举 k，依次开三次根，直到开出整数为止。

题目: 03-Jarvis OJ -Crypto-Extremely RSA

因为e=3，很可能存在小名文攻击，于是直接写脚本进行爆破。

┌──(holyeyes㉿kali2023)-[~/Misc/RSA/extremelyhardRSA]

└─$ openssl rsa -pubin -text -modulus -in pubkey.pem

Public-Key: (4096 bit)

Modulus:

    00:b0:be:e5:e3:e9:e5:a7:e8:d0:0b:49:33:55:c6:

    18:fc:8c:7d:7d:03:b8:2e:40:99:51:c1:82:f3:98:

    de:e3:10:45:80:e7:ba:70:d3:83:ae:53:11:47:56:

    56:e8:a9:64:d3:80:cb:15:7f:48:c9:51:ad:fa:65:

    db:0b:12:2c:a4:0e:42:fa:70:91:89:b7:19:a4:f0:

    d7:46:e2:f6:06:9b:af:11:ce:bd:65:0f:14:b9:3c:

    97:73:52:fd:13:b1:ee:a6:d6:e1:da:77:55:02:ab:

    ff:89:d3:a8:b3:61:5f:d0:db:49:b8:8a:97:6b:c2:

    05:68:48:92:84:e1:81:f6:f1:1e:27:08:91:c8:ef:

    80:01:7b:ad:23:8e:36:30:39:a4:58:47:0f:17:49:

    10:1b:c2:99:49:d3:a4:f4:03:8d:46:39:38:85:15:

    79:c7:52:5a:69:98:4f:15:b5:66:7f:34:20:9b:70:

    eb:26:11:36:94:7f:a1:23:e5:49:df:ff:00:60:18:

    83:af:d9:36:fe:41:1e:00:6e:4e:93:d1:a0:0b:0f:

    ea:54:1b:bf:c8:c5:18:6c:b6:22:05:03:a9:4b:24:

    13:11:0d:64:0c:77:ea:54:ba:32:20:fc:8f:4c:c6:

    ce:77:15:1e:29:b3:e0:65:78:c4:78:bd:1b:eb:e0:

    45:89:ef:9a:19:7f:6f:80:6d:b8:b3:ec:d8:26:ca:

    d2:4f:53:24:cc:de:c6:e8:fe:ad:2c:21:50:06:86:

    02:c8:dc:dc:59:40:2c:ca:c9:42:4b:79:00:48:cc:

    dd:93:27:06:80:95:ef:a0:10:b7:f1:96:c7:4b:a8:

    c3:7b:12:8f:9e:14:11:75:16:33:f7:8b:7b:9e:56:

    f7:1f:77:a1:b4:da:ad:3f:c5:4b:5e:7e:f9:35:d9:

    a7:2f:b1:76:75:97:65:52:2b:4b:bc:02:e3:14:d5:

    c0:6b:64:d5:05:4b:7b:09:6c:60:12:36:e6:cc:f4:

    5b:5e:61:1c:80:5d:33:5d:ba:b0:c3:5d:22:6c:c2:

    08:d8:ce:47:36:ba:39:a0:35:44:26:fa:e0:06:c7:

    fe:52:d5:26:7d:cf:b9:c3:88:4f:51:fd:df:df:4a:

    97:94:bc:fe:0e:15:57:11:37:49:e6:c8:ef:42:1d:

    ba:26:3a:ff:68:73:9c:e0:0e:d8:0f:d0:02:2e:f9:

    2d:34:88:f7:6d:eb:62:bd:ef:7b:ea:60:26:f2:2a:

    1d:25:aa:2a:92:d1:24:41:4a:80:21:fe:0c:17:4b:

    98:03:e6:bb:5f:ad:75:e1:86:a9:46:a1:72:80:77:

    0f:12:43:f4:38:74:46:cc:ce:b2:22:2a:96:5c:c3:

    0b:39:29

Exponent: 3 (0x3)

Modulus=B0BEE5E3E9E5A7E8D00B493355C618FC8C7D7D03B82E409951C182F398DEE3104580E7BA70D383AE5311475656E8A964D380CB157F48C951ADFA65DB0B122CA40E42FA709189B719A4F0D746E2F6069BAF11CEBD650F14B93C977352FD13B1EEA6D6E1DA775502ABFF89D3A8B3615FD0DB49B88A976BC20568489284E181F6F11E270891C8EF80017BAD238E363039A458470F1749101BC29949D3A4F4038D463938851579C7525A69984F15B5667F34209B70EB261136947FA123E549DFFF00601883AFD936FE411E006E4E93D1A00B0FEA541BBFC8C5186CB6220503A94B2413110D640C77EA54BA3220FC8F4CC6CE77151E29B3E06578C478BD1BEBE04589EF9A197F6F806DB8B3ECD826CAD24F5324CCDEC6E8FEAD2C2150068602C8DCDC59402CCAC9424B790048CCDD9327068095EFA010B7F196C74BA8C37B128F9E1411751633F78B7B9E56F71F77A1B4DAAD3FC54B5E7EF935D9A72FB176759765522B4BBC02E314D5C06B64D5054B7B096C601236E6CCF45B5E611C805D335DBAB0C35D226CC208D8CE4736BA39A0354426FAE006C7FE52D5267DCFB9C3884F51FDDFDF4A9794BCFE0E1557113749E6C8EF421DBA263AFF68739CE00ED80FD0022EF92D3488F76DEB62BDEF7BEA6026F22A1D25AA2A92D124414A8021FE0C174B9803E6BB5FAD75E186A946A17280770F1243F4387446CCCEB2222A965CC30B3929

writing RSA key

-----BEGIN PUBLIC KEY-----

MIICIDANBgkqhkiG9w0BAQEFAAOCAg0AMIICCAKCAgEAsL7l4+nlp+jQC0kzVcYY

/Ix9fQO4LkCZUcGC85je4xBFgOe6cNODrlMRR1ZW6Klk04DLFX9IyVGt+mXbCxIs

pA5C+nCRibcZpPDXRuL2BpuvEc69ZQ8UuTyXc1L9E7Huptbh2ndVAqv/idOos2Ff

0NtJuIqXa8IFaEiShOGB9vEeJwiRyO+AAXutI442MDmkWEcPF0kQG8KZSdOk9AON

Rjk4hRV5x1JaaZhPFbVmfzQgm3DrJhE2lH+hI+VJ3/8AYBiDr9k2/kEeAG5Ok9Gg

Cw/qVBu/yMUYbLYiBQOpSyQTEQ1kDHfqVLoyIPyPTMbOdxUeKbPgZXjEeL0b6+BF

ie+aGX9vgG24s+zYJsrST1MkzN7G6P6tLCFQBoYCyNzcWUAsyslCS3kASMzdkycG

gJXvoBC38ZbHS6jDexKPnhQRdRYz94t7nlb3H3ehtNqtP8VLXn75NdmnL7F2dZdl

UitLvALjFNXAa2TVBUt7CWxgEjbmzPRbXmEcgF0zXbqww10ibMII2M5HNro5oDVE

JvrgBsf+UtUmfc+5w4hPUf3f30qXlLz+DhVXETdJ5sjvQh26Jjr/aHOc4A7YD9AC

LvktNIj3betive976mAm8iodJaoqktEkQUqAIf4MF0uYA+a7X6114YapRqFygHcP

EkP0OHRGzM6yIiqWXMMLOSkCAQM=

-----END PUBLIC KEY-----

                                                                             

┌──(holyeyes㉿kali2023)-[~/Misc/RSA/extremelyhardRSA]

└─$

#!/usr/bin/python

#coding:utf-8

#小明文攻击  

#适用情况:e较小,一般为3

#公钥e很小，明文m也不大的话，于是m^e=k*n+m 中的的k值很小甚至为0，爆破k或直接开三次方即可。



import gmpy2,binascii,libnum,time

n=0xB0BEE5E3E9E5A7E8D00B493355C618FC8C7D7D03B82E409951C182F398DEE3104580E7BA70D383AE5311475656E8A964D380CB157F48C951ADFA65DB0B122CA40E42FA709189B719A4F0D746E2F6069BAF11CEBD650F14B93C977352FD13B1EEA6D6E1DA775502ABFF89D3A8B3615FD0DB49B88A976BC20568489284E181F6F11E270891C8EF80017BAD238E363039A458470F1749101BC29949D3A4F4038D463938851579C7525A69984F15B5667F34209B70EB261136947FA123E549DFFF00601883AFD936FE411E006E4E93D1A00B0FEA541BBFC8C5186CB6220503A94B2413110D640C77EA54BA3220FC8F4CC6CE77151E29B3E06578C478BD1BEBE04589EF9A197F6F806DB8B3ECD826CAD24F5324CCDEC6E8FEAD2C2150068602C8DCDC59402CCAC9424B790048CCDD9327068095EFA010B7F196C74BA8C37B128F9E1411751633F78B7B9E56F71F77A1B4DAAD3FC54B5E7EF935D9A72FB176759765522B4BBC02E314D5C06B64D5054B7B096C601236E6CCF45B5E611C805D335DBAB0C35D226CC208D8CE4736BA39A0354426FAE006C7FE52D5267DCFB9C3884F51FDDFDF4A9794BCFE0E1557113749E6C8EF421DBA263AFF68739CE00ED80FD0022EF92D3488F76DEB62BDEF7BEA6026F22A1D25AA2A92D124414A8021FE0C174B9803E6BB5FAD75E186A946A17280770F1243F4387446CCCEB2222A965CC30B3929

e=3

res=0   #res即k

c=int(open('flag.enc','rb').read().encode('hex'),16)

print time.asctime()

for i in xrange(200000000):

    if gmpy2.iroot(c+n*i,3)[1]==1:

        res=gmpy2.iroot(c+n*i,3)[0]

        print i,res

        print libnum.n2s(res)

        print time.asctime()

        break

#PCTF{Sm4ll_3xpon3nt_i5_W3ak}