RSA-OAEP
Published: 2021-01-25 09:51:40

<!--既存のRSA 暗号は，適応的選択暗号文攻撃のもとで識別不可能性を満たさない．
RSA-OAEP 暗号は適応的選択暗号文攻撃に対して安全にRSA 暗号を変換した方式である-->
Existing RSA ciphers do not satisfy indistinguishability under adaptively chosen ciphertext attacks.
The RSA-OAEP cryptosystem is an adaptation of the RSA cryptosystem that is secure against adaptively chosen ciphertext attacks.

<!--公開鍵暗号の安全性は解読モデルと攻撃モデルの二つから決定される．攻撃モデルとは，攻撃方法に未知や既知，平文か暗号文を用いるかという仮定を置いて具体的に検討するモデルであり，大まかには暗号文単独攻撃，既知平文攻撃，選択平文攻撃，選択暗号文攻撃，適応的選択暗号文攻撃に分けられる．-->
The security of public key cryptography is determined by two models: the decryption model and the attack model. 

The attack model is a specific model that considers the assumptions of whether the attack method is unknown or known, plaintext or ciphertext, and can be roughly divided into Ciphertext-Only Attack, Known-Plaintext Attack, Chosen-Plaintext Attack, Adaptive Chosen-Plaintext Attack, Chosen-Ciphertext Attack, and Adaptive Chosen-Ciphertext Attack.

1. Ciphertext-Only Attack(COA)
2. Known-Plaintext Attack(KPA)
3. Chosen-Plaintext Attack(CPA)
4. Adaptive Chosen-Plaintext Attack(CPA2)
5. Chosen-Ciphertext Attack(CCA1)
6. Adaptive Chosen-Ciphertext Attack(CCA2)

<!--解読モデルは暗号文における解読の困難さを保証する性質であり，Onewayness(OW)，Semantic Security(SS)，Indistinguishability(IND)，Non-Malleability(NM)に分けられる．ただしSSとINDは等価であることが知られている．-->
On the other hand, the decoding model is a property that guarantees the difficulty of decoding a ciphertext, and is divided into Onewayness (OW), Semantic Security (SS), Indistinguishability (IND), and Non-Malleability (NM). However, SS and IND are known to be equivalent.

1. Onewayness
2. Semantic Security
3. Indistinguishability
4. Non-Malleability

<!--まずはCryptoモジュールをロードする．入っていない場合やGoogle Colab等の環境で実行する場合にはpipでインストールする必要がある．-->
The first step is to load the Crypto module. If you don't have it, or if you want to run it in Google Colab or other environment, you need to install it by pip.

```Python
!pip install Crypto 
!pip install pycrypto 

import Crypto.PublicKey.RSA as RSA
from Crypto.Cipher import PKCS1_OAEP
from Crypto.PublicKey import RSA
from Crypto.Hash import SHA512
import binascii
```

<!--モジュールのロードが終わったら，次はRSA暗号を実装するためのインスタンスを作成する．bitは9216に設定して，RSA暗号で使用するe,d,p,q,n,uの各値を設定する-->
After the module is loaded, the next step is to create an instance to implement the RSA cipher, setting the bit to 9216 and setting the e, d, p, q, n, and u values to be used in the RSA cipher.

```Python
rsa_fact = RSA.RSAImplementation()
rsa_key = rsa_fact.generate(bits=9216) 
print(f"e = {rsa_key.e}")
print(f"d = {rsa_key.d}")
print(f"p = {rsa_key.p}")
print(f"q = {rsa_key.q}")
print(f"n = {rsa_key.n}")
print(f"u = {rsa_key.u}")
```

```
e = 65537
d = 54712778709843758446774472112947462605632784372693122692337276261706132343656126613850926869326406853031970937071342771082822051125805156814265100039334033193394094696992133614788847524124626876788542754592152526755990085909097407899383965497160111603490967247421144341240388433715972885769118066232454391706407281337508657486450869604612564915186037245926381485539948826749394883310642506522860818664271873435204459633736609361644611422172966074295803766199657927782114843907265391913377990158502268099171524921346814639644811634440213721098581488684823081553716072399909286975689372830754895978161079557740719349489560157014980070304726939194392515589389021598696807451490025331025472197541696176574536959564303309782584754250421256847013629445055202895707583429013726974641572883140706464114649362282002536217020801728046128596891191308549622359954181692893371397911637301634686429007441755812855730453915884304296900810588878381229626826762914932745596513434539904181264409311386739871120866568366112158792401213076791241640316240227716212342340269517372470349100996450241482980418865133120619705113594803125536458461903619411425887272770066832982698961431770946272179026490471026816477218733565162061250660114444677999978434132079969423273815362068487751387394001307409566746300482655950466254595004445848729603426974921743117321067583048597487994378747311788421673087176130320191643106706361050698733121878677309152032982200158816636173380076359282229190818958256050449423833086070508663202237289102343430444821667542376265505316574669575266888317615128990541614257673495565638717070299695356619528982437194031623223088997989273538527254541439966436390623411911288976594498254117975827186468761820788181917166160655908222038793192188787506057536765607981183236859861486667943287248863826085430979006295460903969125791512868790008624781444689451536552698147817497993529092563912042411447572632795718879409128809355718412607317831057712125337650191691644798974837098670800670701720810017663061318642521588450469140323451770630715595160815378232359863222296870117263678477582812648780595241664724700622530881004222017746966822917700708971417727097797617274650711675753090288153743294368349630966560446422220442000918908188890792339274543542052469683247718010214669699817444469516823417411264300171803938680624000616913222168448190238169463586309217889800457740939560491028217682579223583692099585650500567564310601363376397288638834272224138612305281785850918201163739271142648677843587525732067833869534084619217243476545179795365399703843687277297783992127210539155348404705206088773242790273376856944095440344175614153608432945927894754645537955829484068839908334168255572223279897229878546502328722404499946139267249915380158535466834444509333020445069897893353705865
p = 12130072046886278833181693082100614705209490447837726916478795788322960425187433549273910811163858383006895211566493794758543314214469285471236812510994877816735418918530066077217991730693600041466398450508367310195026540236275364218960767726620386759305379726879156874372965815470952269630302500173347327737693854988729268125509953762486822230357042090218143277836388276304773217375314690742789099130276227817495338520710275364341485155649268557827356048679509841643856093386007904154178133172759581155257670650028891335450188812289959428036381574569572848288535147607757369434016439509738989561427640240846187462354047641648721167182151585825057563180217175344933304090734367449738582350990303309378180110441897589353963213209371167770839804116617001521473687963876715344669709618814276909295668483541284565699994873849455930797486697856953941240424898746290877655182663159735474084712028149263972582942278156444963327822302574036936538681387111065077622844779223675297781440327259496102826382911113441313895030709814775627366783374611349731038590334887254584403840920672527132497102789239488068413183210713915507467132039515076945406086964071206518087086227370462515386332255612649671257472939512949302542353425786572795169262367563943848996139195471409494525329479762489213230006644732987840867198923512825208227632540582309134086997973750198226191910215295385938719089111438470634629
q = 12519805089236855940644210164209487623056371482442480033891581785951665924652122387636234172969095523357832081173146423080702422310354655826250129936269506566322422748900965223409189685589013330288514205723610286815010104443004435906187760806971871410953314908142729011749321942800951734468583784583950464476258455128461462235794149719745985882483978225051023582170954741174070891339318418665713855921985629953661579695382235034076281235217675973909551120871901574560206528446274641484268876807337164011673574772349829718276881142444789314205845707277490045469191728542280765995963818552845065797299975252921830778632300367309810556300770135093908113204393740605060086069333971785454040389147500355972790011429678646857816729014936550909634890407619686980073019768893724302757522559371788273933025350731188260796680491797869578748755298530752042259929172172073220561245954937796837582346075129004838903435323759761168335338503154239996870811663325163467144633044444683305828032595987699706984427334806391388798223770770759146765627296261487267519617152876345941957791634282765073377692982823376414652977870529648753561689121940883129724099795198962660636134643368278840349884630792737349208594102964824563232263117048499819487289804609056850410444299774680189540308196827320365488901128335582300667298664516455480259598865327627717566900947312780072998889331304668363400401827709600071239
n = 151866137745416559964688432462252249239140899980229095840401002683640455525229408745582490967559388671685073876703425995868659047250514275640019137744180023438036033380914550875118237270278923875485609525547664230486100642083118750645967004649840423283977278408125006848158542068546174029674757134669279720014519249375981740955043439129113280540703372283523665385533506681575328976643495741391246854127329878841344910042615567647880348090930061310877306824167844716998706557331347761205669109356561058168455560068201524333505654994973033189599666893563900313234758808897245137458208226132276634522923326880507116344394447673130775861571339181482482838261055792152547230949485485160281918233462798793958977964464264368862871417530382360339787905338214511548684422311095363378810078439811633541090245023754843090765104920708608662481659311540740188920601296243579385934731056449842549849555745641891793062841823104046872474203700111069867691048475759431932072284145501744963259734574577644781400543487823891091049832633154617237871390683825498174930327145964170919879252551961351745800165650088065988463598732057618833716412594871261980363991170720004793830919289906082158307435479479890071215428577428318411256808772197740971775301245780566519550041818808287737185025651759082663836868185668672470752081352181931650163897914338498101726771682277579669251094827096382101189662202450247528706801595182126253780755239694355924054815116591597638863241923224957759401328356378516951298552036613701403430346061627363679308261625674587619186822019969489756671012716817953167343781500006912276898198404318225817544624942139706545510714957768405724130224044295151751258549947354541150305045790078113589355945586278683046582782171793878106819223191188021984804727473789164194402818429740290591778754298559738921522474090291994429142317273233206117290986481681738738095664842469126723615623734749386881345694943175511880029898076319845417819110458926783344321175294806398526366996857765614996690254307549487134315691991028833945558109920098447456971122417762047751568805600928997384384901221399979066351526851503503362633626878650964501615886068743543944340472537664872044563469147981087766547141773072969618866988862626405646237369965807693949174786994560543281886370835506173995971701526182793145750359730095459848775071019405310123102485875350194023236625930364934091839491472058169530377591119011866264555545140737823811539715806258841365400919854827823652643926926193766906212264774344672386155195669948088831284534824735348516353444624174191126137172153322802381084234378129779213443880989004389935095956015922766705668107643657680934715125161267797159590647680270188197204888730459846953067030083669037671381538306240840673142093309452688601121676213823304404229039280947940335331
u = 10781822158372164742305626294850686816831936241525441028001043230411582088038973667162094571894187799999749147562041473604748123629150416928301030140990157623156390638612027288675572338366206717697612690947583061508263153619828286332612888722304000580433813985435206665463379094804702738936656626553314167402691854837491124299938995328452085547321260975589522866500856536443154265563359114784492581927028546354540248880733201762730703819908738348842889637325263821921965997752379810807238918240061069181254153221962474923573838098699018734758805819683376921483153685826373880726336969800504033784742731823112064241774768842814076116633600658679876600047133526288364915626666661753097150236067251142522143737634832651262466849731567407483241432201831247209145398769142292010779623659758305502902229581712596101308986885819673232808246175699681672202309156701075927859899886829767012503005194934421294783981572466821103049254421135653208178444947763051815002282479680402390074943146793557595444822691075774625011960189188631315907051066786786183550298038765045896809870184328342874576998223471703093795866581191011541245524753621535560250397713625184569644431536651498541155015903163493369214406453958554598704502289203541177059659769715495474329271405160176325178717639725228119763163665086490064099329801540922235306326637478727213854429773502229254532779759856101596122507840306436792107
```

<!--次に上で作成した各値を暗号化する．なお暗号化の際に用いるハッシュ関数はSHA512を用いる．-->
Next, each of the values created above is encrypted. The hash function used for the encryption is SHA512.

```Python
message = u'This is plain Text'.encode('utf-8')
P = binascii.b2a_hex(message)
key = rsa_key
cipher = PKCS1_OAEP.new(key, hashAlgo=SHA512)
ciphertext = cipher.encrypt(P)
ciphertext
```

```
b'G\x82\xed\xe7\x00rH\xb0KF\x8c\xd7-\xafz@\xe0\x8b\x01\x7f\x1f\x8f\x19\x12- \x83\xc6b\xd6V)^\x10\x14\xaf\xa11L=\x93\xba\xa9\x86r\xda2\x99\xa1q\xc8\x97X\xf7P\x8d\x94\x19\xf9\x13*\x13c\x8fD\xa3\x90\x18\xcc\xf9\xcf\xa1jF\x91Z\xe3^r\xb8\x08\xb2;\xb4\x8f\xd0\tf\x18\xee\xda\x0c\x81\xa1S\xf1\xbaZ\x00\xdf\xab\xcf\xb2\xbeW\xc4\xb1\xba\x8a\xbb\xd6\x96\x1f\xac<Q\xa93<\xaf\x99\xc1\x82\x86\xe0\xb3\xbf\xb6,\xf0\xf7\xe0\x98\x19\xa2:\x1fC\xa5W_\r\x99P\xf9\x80\xe3\xeeXy\x14\x88\xfaZN\xd3\xa3!\xcdv\x98\x9fi\xc1\xb3\xd06\xefKx7\x1c\x8d\xd8\xa5z\xb1|\xf8k\xdd\xfc\xce!F\xcb\xfd\xff++\xa7\xf9\xed.\\\x14\xa9\xadc\xd7\xbf@sW\xa5\x94\x9a\x8eB\x05\nk\xc8,\x19\xd9\xb6\x8aY\x92\x86\x17Y\x89\x02\xbfJ\xfe\xd9\xf8A=@\xba\x87\xc2t\xdb\x1f\xd3K\x0f+3\xdfK-4B\xca\xfe}\xd6o\xef\x04GL!\x9f\xee\xe0\xd4{\xee\x07F\xf1\xc9\x82F\xe2Y\xa5\x15\x11.\x88"\x12c;\x84m(\x15h\x89\xba\x1b\xab\x8a\xdc\x844\xfd+\xaa\xbe\r/b\xa5\x08\xa9\xa4\xbb\xb9\xe5\xcdl\xcc_\x9f\x01\x9dP\xed\xe7\x9db\xffF\x14+y\x07\x95\xc8\xd4c\xe7\x98SZC\xfc\xc30\xcf\xa7\x1a6bAUqp\xeehP\xa7Hr\x80UP\xd7\x8dM\x97\xd9\xf0\x18\x02t"\xa0\xeawdL\xc1>"\x1e\xed!\xfc+\x1f\xa3\x98\x1acXd;\xb0\xd4\x904"\x9a\xf6l\xc6\t\x8a\x9d\xb3\x83\xb0p\xc0\x8f6\xe3\xcb\x185\xf3\xba\xf1ux\xe3\x81\x05\xad\xe4>{\xf4w\xdaN\x85\n\x87 \xf6b,Dk\xb0P\xc7\x9e4\xca\xed[9\x14\x89tRF`\xcfC\xc52\xf5\x022\x94! \xef\xd6lU\x8ev\xec(V\xff\xe0M\'vM5\x8e\x8d\x96\xd0Sc~g\xb5\x03a\x1e\xfd_q\xea\xf0\x8b\x9e+sTE\x14\xfd\x8fr\x16a\\\x1cC\xeev\x0e\x13nv\x9e\xd4\x94,\xbc\xa5F6\x9d\xfa`\x04\xf3Xl\x03\x9f\xad\xb8b\x9fI\xf1\xad-\xb1\x06\xbb\x9a\x13C\xa4^\x89O\xf4S\xf5M\xe2m!\x94\xc2\xee<U\xa1xo\x9c\x01r\x8f\xce\\\x11\x18\n\x0cN\x9bhyQ\x03\x04\x005z3\x0b^\xe0\xcc&\xa5\x01\x0c!\x10\x9a\xed5\x87$,! \xe8vq*\x17\xa2\xe4\x05\x93\x015\xa7%\x89\xc6\x0f\x80\xb8\xb1e`I\xc5^\xb7?\xba\xdfh\x1a\xdd+\x14\xd2\x13\xc4\xf1\x98\xfa\xde\xc8#A2\xad\xcf\xcd\x7f\x85\xd1\x8f\x12Z:\x1b\xe6\xcf\xe4-I\xe0M\x93\x0f\x93\xcemq\xedP\xd0zX\x8b7\x84\xc7\n\x96\x95\xbd\xa5D\xaf\xca\x8e_\x9cw\x05\x1d\xb8~4aE\x0c\x96\xe3\xc8"A\xfb"\xc0\xfb\xb2\xf3\xb7\x06\xea\xaa\n\xf17\xe0]uUk\xdd\x85N\xa8\xbc\xeaF\xe8\xc6u\xcb;\x89I_q\xe0^9%\x9ae\x82\x849=\xb4)\x04\xd9\xb9*\xdf\xe1\x93\x84\x83\xef0\xb6\xa5\xf0\xdd<\xce?\xadh\xc6\xb6\x85\xc7\xa1\x9b&\xad\xf5\xb3\xca\x19\x9d\xccT\x11r\xe5\xc0\xc6\x0b\xb8,:~\xe7\xcc\x12u\x8a\xa6\xe0\xce\xf5\xca \xfd\x00\x88\xf5\xf93\xb4\xe8\x89\xd94\xf7\xbf`\xc3\xa5\xc7\x9e\xd3Y\x1a\xda\xcfC\xad\x80l%b\xa0\xd8R2\x88\xfeM\x08\xdc?\xc1\xa2\x01F\xa9\\8\x07i\xc0\x04\xe3\x1f\xd3\xa5\xfa\xde\\[\xd3\x1eg2I\xa4\xcd{Ej\xff\x14\xf7g\xac\xc0\xf7\x82^=\xad\x88\x83\xb8\xa8\x84\xe1\x98\xf8\xc8\xa9\xe2TV\x82\x1cfy\xf5\xcf)oB\x18\x85<\xb7\xe9\x8a\x84\x90\xb8\xd6;\xba\xf0\xc6\xecf\x8b\xdf_,9\xf2\xbf\xd6IuI\xf2\xb8P\x06I\xa5\xaa\xd5WY\xbd\xd1\xf6\xf1B\xba\x11\xd5\xf7\xc7\xd2%\xfc\xa8.\xe0\x15\xef\xbf\xdb\xd1\xebNp \x86\xaa\x15\x1dv\xee!C,\xa1$\xa5\xe9_aI\x01\xb8\xb0\xb9\xa6Z\x97\xf1l\'\xee\x82\x04\xcb\xaf\\p\x0ef\x9b\xb8 \xdcoD\xb8\xc6\xa3\x1c\xe5\x17[\xb4\xc7Q}(\xb8\xb9G\x81\xd6jj\xea(\xb5\xf2\xe6\x84\xd0n\xf9}\x1e\x9f\xe4\xbc\xae\x1d\xd1\xe0\xbf\x97\xfa^\xcb\xb9oc/\x84H$\xe2\xb33\xa6\xd9\xc6I\xe7\xbe\x01[\xff\x95\x12\xcf\xc8rl\xb4\x14\x80>f|\xf0\xb5E\xe4==<b/\xbe\x90\xaa\xbfp\x80\x84\xa2\xa8\xe2o\xf6lR\xfaQ\xa0w\xd2\xbd\xecU<Z\xa2\xc1\xbf\x8b\xff\x1eN\x88[\x9c\xa8\xe8i\x7f\xea\x84\x80\xd6H\x91\xa5\xa6\xbe\xff\x18\x0197\xe239\x16\x0f\x8f'
```

<!--最後に上で作成した暗号文を復号する．なおノートブックで実行する場合にはセルにマジックコマンドの%%timeを一番上に追加することで，実行時間を測定することができ，暗号化の場合と比較して10倍近い時間が掛かることがわかる．-->
Finally, we decrypt the ciphertext we created above. When running the program in a notebook, you can measure the execution time by adding the magic command %%time to the top of the cell, and you will see that it takes almost 10 times longer than the encryption case.

```Python
M = cipher.decrypt(ciphertext)
message = binascii.a2b_hex(M).decode('utf-8')
message
```

```
This is plain Text
```