羊城杯 RSA & Number Theory

羊城杯 2024 - TheoremPlus

题目内容：

相信这里的Theorem你也能知道^V^

题目分值：

已答出0次，初始分值500.0，当前分值500.0，解出分值500.0

题目难度：

中等

from Crypto.Util.number import *
from gmpy2 import *
from secret import flag

def decode_e(e):
    if e > 1:
        mul = 1
        for i in range(1, e):
            mul *= i
        if e - mul % e - 1 == 0:
            mulmod = mul % e - e
        else:
            mulmod = mul % e
        return mulmod + decode_e(e - 1)
    else:
        return 0

q = getPrime(1024)
p = next_prime(q)
n = p * q
phi = (p - 1) * (q - 1)
e = abs(decode_e(703440151))
c = pow(bytes_to_long(flag), e, n)
print('n = {}\n'
      'c = {}'.format(n, c))

'''
n = 18770575776346636857117989716700159556553308603827318013591587255198383129370907809760732011993542700529211200756354110539398800399971400004000898098091275284235225898698802555566416862975758535452624647017057286675078425814784682675012671384340267087604803050995107534481069279281213277371234272710195280647747033302773076094600917583038429969629948198841325080329081838681126456119415461246986745162687569680825296434756908111148165787768172000131704615314046005916223370429567142992192702888820837032850104701948658736010527261246199512595520995042205818856177310544178940343722756848658912946025299687434514029951
c = 2587907790257921446754254335909686808394701314827194535473852919883847207482301560195700622542784316421967768148156146355099210400053281966782598551680260513547233270646414440776109941248869185612357797869860293880114609649325409637239631730174236109860697072051436591823617268725493768867776466173052640366393488873505207198770497373345116165334779381031712832136682178364090547875479645094274237460342318587832274304777193468833278816459344132231018703578274192000016560653148923056635076144189403004763127515475672112627790796376564776321840115465990308933303392198690356639928538984862967102082126458529748355566
'''

起手式：分解整数n，这个不难

分析decode_e

def decode_e(e):
    if e > 1:
        mul = 1
        for i in range(1, e):
            mul *= i
        # mul = (e-1)!
        # e is prime <--> (e-1)!=-1 % e
        # Wilson theorem
        if e - mul % e - 1 == 0:
            mulmod = mul % e - e
            # mulmod = -1
        else:
            mulmod = mul % e
            # mulmod = ?
        return mulmod + decode_e(e - 1)
    else:
        return 0

这个函数一般来说计算会很慢，根据数论定理，将其简化，然后加速计算

整点简单数据测试一下。

from sage.all import *
from Crypto.Util.number import *

p = 137005750887861042579675520137044512945598822783534629619239107541807615882572096858257909592145785126427095471870315367525847725823941391135851384962433640952546093687945848986528958373691860995753297871619638780075391669495117388905134584566094832853663864356912013900594295175075123578366393694884648557429
q = 137005750887861042579675520137044512945598822783534629619239107541807615882572096858257909592145785126427095471870315367525847725823941391135851384962433640952546093687945848986528958373691860995753297871619638780075391669495117388905134584566094832853663864356912013900594295175075123578366393694884648557219
phi = (p-1)*(q-1)
n = p*q
c = 2587907790257921446754254335909686808394701314827194535473852919883847207482301560195700622542784316421967768148156146355099210400053281966782598551680260513547233270646414440776109941248869185612357797869860293880114609649325409637239631730174236109860697072051436591823617268725493768867776466173052640366393488873505207198770497373345116165334779381031712832136682178364090547875479645094274237460342318587832274304777193468833278816459344132231018703578274192000016560653148923056635076144189403004763127515475672112627790796376564776321840115465990308933303392198690356639928538984862967102082126458529748355566
fake_e = 703440151
for i in range(-10,10,1):
    e = 36421874 + i
    try:
        d = inverse_mod(e,phi)
        print(long_to_bytes(pow(c,d,n)))
    except:
        continue

对于这个函数，递归进行，现在已知decode(e1)的值，计算decode(e1+1)，

若e1+1为素数，则mulmod = -1，恒定减去-1

若e1+1为合数，则mulmod = 0（除去一个个例）e1+1=4时，mulmod非零

小范围实验，然后直接猜。ok

(n-1)!equiv 0pmod{n},quad n>4

Back