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
```python
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
```python
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にしておいたほうが良いと思います。
参考文献のコードを参考にして作ったのでほぼコードが同じになってしまってます・・・

## 参考文献
https://qiita.com/motimotipurinn/items/915fbae5b2e0bfaf8877

https://tech.kusuwada.com/entry/2021/04/08/121120

etc.