s上次的黄河流域赛遇到了一道需要将运算域扩大的问题。这种情况在第二届“长城杯”网络安全大赛中的RSA也出现了。
题目源码：
from Crypto.Util.number import bytes_to_long, getPrime, isPrime
import win32gui,PIL,numpy,operator,pymouse
from Crypto.Random import random
from random import getrandbits
from sympy.ntheory.residue_ntheory import nthroot_mod
from sympy import nextprime
from secret import flag
def get_primes(m):
p = getPrime(Bits)
pl = p & int('f'*(m//4), 16)#p&(2**(200)-1)
q = (getrandbits(Bits - m) << m)^^pl#rand+p的低200bit
while not isPrime(q):
q = (getrandbits(Bits - m) << m)^^pl
return (p, q)
def get_key(p, q, delta, beta, Bits):
phi = (p - 1) * (q - 1)
d1 = getPrime(floor(2 * Bits * delta))
e1 = inverse_mod(d1, phi)
d2 = nextprime(d1 ^^ getrandbits(floor(2 * Bits * beta)))
e2 = inverse_mod(d2, phi)
d3 = getPrime(floor(2 * Bits * delta))
e3 = inverse_mod(d3, phi)
return (e1, e2, e3, d1, d2, d3)
if __name__ == '__main__':
Bits = 1024
alpha = 0.098
delta = 0.536
beta = delta
gamma = 1
m = floor(2 * alpha * Bits)#200bit<n^(1/4)
p, q = get_primes(m)
n = p * q
assert n % 2^3 == 1
u0 = nthroot_mod(n, 2, 2^m, all_roots=False)
v0 = (2*u0 + ((n - u0^2) * inverse_mod(u0, 2^(2*m)) % 2^(2*m)))
e1, e2, e3, d1, d2, d3 = get_key(p, q, delta, beta, Bits)
flag = bytes_to_long(flag)
c = pow(flag, e3, n)
l0 = d1 - d2
print(f'N = {hex(n)}')
print(f'e1 = {hex(e1)}')
print(f'e2 = {hex(e2)}')
print(f'e3 = {hex(e3)}')
print(f'c = {hex(c)}')
print(f'v0 = {hex(v0)}')
print(f'l0 = {hex(l0)}')
# N = 0x62c048bc886075bffb9ad01255786dd8ef2480ba510f13689c1e84ffaaf21dfb5695a4d83f4ba22093bdd75bfc8f5979185d29724ecccf045e1857b1b2a4757dd82dc44318c054c9fce9bc451e6beecb97bbda6562420fc8c295521c5455443413f90403cf1af6271fb6d2d54378b86ced18ae6844a877890ea853a215880a09c68c517a75c1183c067b706ce630f3f0913591f7354cfa60c8f6b7ab2f15e466a1ea6e8034417a5fc3c11b8ba746596c22c734b09257e9a6fb18358738d416eda0ba0e7b028dd2d550b1e018b180916ac25f47910657a5db2410946c0593b7e23ed1659a811083f363ad4eb65642091a040befbd643089bbee376634d2394d11
# e1 = 0x124241a12ea2be53f9b9b1fd92e10d089cfa32aa07e6c2cace848aaa6c73ff06d4c6c92b7d1f29160b2eef95a5f580915d3f15c0ea23975cbadfe8347a10daab2bd0827d7e909b329ec53c5eb306f0a5125b3817e7ea0c15b2317a46c36c4f34fc626dadc6c769bcc7be18ddf7954fae8dde3fd4ce3c5146c019bdb0d9552af1dc9ef7186e06b1d59e763fb05c7cd21fbb3f509fee52d4e24921ebfa76bb8302ea6760e92606e440907cc1c110946af53900904e84dbc309fcef15ea060c667070e5e0310891606df151609ff609bcc6125c6043c35119b25df78b4d5ca61ab6492753cc5e5b32e044fce0aeb0442464f36298add254e9fb6505fa4cddae1cf7
# e2 = 0x17b3937cec3ca5fdddad8db29c6dc4efae1408bf5b4aa2ff602112c50f302e9698c79c7ab79fef0210c621dcc218d91d358b7f93a978c4e3f2b982794697c4797cef89189d1464ed1c767bf72433092922352885f8e355952c558ad2c9ade58a19375ddc5dcf3f9fa28c68a5cff158734d94224b85f77bd939133f39ab7884ece61d9fb3496373008827c2ae694dfe7da08eee348ef99c3a6737a4b088b62978cf209ef3d1140a30d42872615b94378108266e3d344caf51b497a585a4b5ef8619cc46959bad9b89f59f36175fbf9b64363443f3f7743896c72a198decedf89c518fa07b1d401d0359578a4926b7d67de86232ee24751f17dafbc749c0783b33
# e3 = 0x5647c4490bda9e7e497651551600572c5ef4e2d889b9b1ba0e9a493660497e10877e975c01da9aebae5e3ba9aad976a1a783b39191e8fd799689dfa26b069264d60543602d514ac412ac75d827d67c78ad544bda633f0fa69fb5bbc37e0f6b95714576ff53bae3f7f991d143a4b1e841730d5d580d4effeb8fb02e8b3c3c9a1f1899d2eb411ce37f16d30cfa1f7af7322be4f42f5d012f484a1181fa4aa0b5f420a472030a5c08c80bff76ab82ef5768bfd495abcdc5f22aae1891561322dfb28ff63c4e467411c8b73c11d64b05f411e2a1de0c7754c6a62d1f72cded9e2592ccc21be3fce4ea6f083a617a246fd3fe464ef2487adbfabfb628c882ea991675
# c = 0x45f2ee650d622d1e0f0e2e2e861001e9866c541f9f1dd2ec1dec18194f8b7224914916ecd68bbc74b28a000d2664e671586aed63b54c0928a939caf28d39eeba03c0ce3afcf2cdc5805e8e2792d76e88545aa4dee11078ba1e2e5b56ee23d58e443d7aff180d4e7463ae66ea8e96e0c8d4e1443e7664b99599af14e591e28cf2f833bd30b44b89c396b5fc1ee81ea3f7bc08dab426b1871eb66829c81d57e2ebf5c7a3e9c593ce496f0b0c4237906b019ae75ca551d6b0b1adfe64958c2ead6c39e517eb75eaf4b4d72402bea40f043cf0a80317aa2f1a996c727e195e15f903c0cac618f668af1015ee479d1c7b1c1b370fd4a5a76f5bf295e6bd7d0f4ae56f
# v0 = 0x2c77a013f2595a90c4e10a53a0f863d02b361c7407dad7d59db7c98df427da00c8d8627dbaef9557279ca31227cdb402d2d2
# l0 = 0x3dbabf6ea5b801221c283bd234f04264d292c8f3048c8b59c21e003cda983a3a41e4392c6ea77a706631de60d261f2b367027e037d37fda5a13a8e01b2c6c0f48a3112315cffe7420a50a3ebada09aba61f8e6da793654a467b9f780c20c5085012e064ab9205c076073b4fb4895e01d0d568fd5c30159879180093855d39d5548a1389a94f57c680c
细节处就不说了，通过代码可以得到下列关系：
$e1d1\equiv1mod phi $
$e2d2\equiv1mod phi $
$e3d3\equiv1mod phi$
$ l_{0} = d1-d2 $
由$l_{0}$猜测从e1和e2两行关系入手，推导如下：
$e1d1=e2d2=e2(d1-l_{0})=e2d1-e2l_{0}$
$\Rightarrow (e1-e2)d1+e2l_{0} \equiv 0modphi$，两边同乘e1（凑出e1*d1）
$\Rightarrow (e1-e2)e1d1+e1e2l_{0} \equiv 0modphi$，化简
$\Rightarrow e1-e2+e1e2l_{0} \equiv0modphi=kphi$
在扩大域$kphi$上有，$e3d^{‘}_{3} \equiv 1mod(kphi)$
又有$c\equiv m^{e3}modn \Rightarrow c^{d^{‘}_{3}} \equiv m^{1+k^{‘}kphi}=m^{1+k^{‘’}phi} \equiv mmodn$
解题代码：
n = ...
e1 = ...
e2 = ...
e3 = ...
c = ...
v0 = ...
l0 = ...
kphi = e1 - e2 +e1*e2*l0
d3 = invert(e3,kphi)
m = pow(c,d3,n)
print(long_to_bytes(m))
转载请注明来源，欢迎对文章中的引用来源进行考证，欢迎指出任何有错误或不够清晰的表达。可以在下面评论区评论，也可以邮件至 1666739907@qq.com