RSA暗号のeは大きすぎても小さすぎてもいけない

目次

• RSA暗号の簡単な説明
• eが小さすぎると解読される
• 逆にeを大きくしすぎてもやっぱり解読される
• まとめ

RSA暗号の簡単な説明

桁数が大きい数字の素因数分解が難しいことを利用した公開鍵暗号の1つです。

• e,p,qは素数
• n = pq
• l = (p-1)(q-1)
• d = e^(-1) mod l
• 暗号文 c = m^e mod n
• 復号した文 m = c^d mod n

eが小さすぎると解読される

eが小さすぎるとLow Public Exponent Attackを適用した解読ができてしまいます。
尚、Low Public Exponent Attackが適用可能な条件はm^e<nのときです。

picoCTF　miniRSAより引用

N: 29331922499794985782735976045591164936683059380558950386560160105740343201513369939006307531165922708949619162698623675349030430859547825708994708321803705309459438099340427770580064400911431856656901982789948285309956111848686906152664473350940486507451771223435835260168971210087470894448460745593956840586530527915802541450092946574694809584880896601317519794442862977471129319781313161842056501715040555964011899589002863730868679527184420789010551475067862907739054966183120621407246398518098981106431219207697870293412176440482900183550467375190239898455201170831410460483829448603477361305838743852756938687673
e: 3
c: 2205316413931134031074603746928247799030155221252519872649649212867614751848436763801274360463406171277838056821437115883619169702963504606017565783537203207707757768473109845162808575425972525116337319108047893250549462147185741761825125

以下のコードで解読することができます。
環境：Python 3.11.1、gmpy2 2.1.5

import gmpy2

def int_to_bytes(x: int) -> bytes:
    return x.to_bytes((x.bit_length()+7)//8, 'big')


def LPA(c, e, n):
    while(True):
        m, b = gmpy2.iroot(c, e)
        if b:
            break
        else:
            c += n
    return int(m)


def main():
    n = 29331922499794985782735976045591164936683059380558950386560160105740343201513369939006307531165922708949619162698623675349030430859547825708994708321803705309459438099340427770580064400911431856656901982789948285309956111848686906152664473350940486507451771223435835260168971210087470894448460745593956840586530527915802541450092946574694809584880896601317519794442862977471129319781313161842056501715040555964011899589002863730868679527184420789010551475067862907739054966183120621407246398518098981106431219207697870293412176440482900183550467375190239898455201170831410460483829448603477361305838743852756938687673
    e = 3
    c = 2205316413931134031074603746928247799030155221252519872649649212867614751848436763801274360463406171277838056821437115883619169702963504606017565783537203207707757768473109845162808575425972525116337319108047893250549462147185741761825125
    
    m = LPA(c, e, n)
    
    flag = int_to_bytes(m).decode().strip()
    print(flag)

if __name__ == '__main__':
    main()

逆にeを大きくしすぎてもやっぱり解読される

逆にeをものすごく大きな値にしてもだめです。wiener's attackを適用した解読ができてしまいます。

picoCTF b00tl3gRSA2より引用

c: 68978016775130675267397253288365069937494395958827976139045628283797897583610138433615795050154109242094322116828936672671897455812868286838566145513659193766982435756453870936236023639565827720164322007951592617324952181926575414879669005655497556492509318794275858427127925160284304375094577145732456956899
n: 104351642176788068445510852552998236867662303793264870337706588081767022854724901853167273753032126225311761340670292256485721005396692702365045739114025944358968113095678814461465394608377410595373298202970089660094030338793155582625310221360030297667063595018133237512426443179762491808773379097087660810773
e: 33817912449346198112733341431147741776893658090317722524719627451190164310412472198291342710845008604290652594938681008216736018334991780300154209882094032352589815631119795272176683304884026082584627329351980173226868150012096559097555429894657396188919315056318303669752231046639988931670771824043199060213

以下のコードで解読することができます。
環境：Python 3.11.1、owiener 1.0.8

import owiener
from Crypto.Util.number import *

e = 14657862679929821001806452844506264567056350556634338429898130430900010471868786662352322627602034875845627080965460498232196513435708740682575483515196992518627742738606056702829144417998392263372724779034919215928566761112799064998168364805394830790290432463357562850348022204623708394249782834214570206771
n = 95930877214326664770213034849808719167526110432164596999125685657127859926805389971858469384381118848484140282456507663854436982695723835363771728423804969685183378278052121379375360577355390961013827223956410541039594777146435521550955411008897073426704729624479660095091260460537825715342859102311428164269
d = owiener.attack(e, n)

if d is None:
    print("Failed")
else:
    print("d={}".format(d))

c = 20238498147817592588655474604364588636895051939574031415504486045450613986230040851394515198143931360251495245657504028763213870473980494969521347446958620562261145919547805851533162483005163148905048336017330184091366597748490760442967717517358979809870985377207031656560276154692304834163528018891283538720
plain = pow(c, d, n)
print(long_to_bytes(plain).strip())

まとめ

eにこだわりがなければ、e=65537にしておいたほうが良いと思います。
参考文献のコードを参考にして作ったのでほぼコードが同じになってしまってます・・・

参考文献

etc.