Ciphertext in Python: IND-CCA2 and RSA-OAEP

Cryptography review

How do you evaluate whether a proper cipher is secure if you think about it? The teaching of cryptography is to first consider the enemy who breaks the code, and then to the extent that the code is broken.

Attack model

• CPA (Ciphertext for arbitrary plaintext can be obtained)
• CCA1 (plaintext can be obtained for any ciphertext)
• CCA2 (Plaintext for any other ciphertext can be obtained even after viewing the target ciphertext)

The enemy's attack ability is stronger at the bottom.

safety

• OW (one-way: difficult to obtain plaintext from ciphertext)
• SS (Confidentiality: No partial information in plaintext is leaked from ciphertext)
• IND (Indistinguishable: Indistinguishable between plaintext A and B)
• NM (robustness: given a ciphertext, it is not possible to generate another ciphertext with one relationship)

The lower you go, the more severe the conditions.

What is IND-CCA2?

The ciphers we seek maintain strict security standards even if the enemy's attack capability is high. Therefore, I would like to verify the conditions of NM-CCA2. However, the condition of NM is difficult to handle theoretically. Fortunately, CCA2 proves that IND and NM are equivalent. So you should consider whether it is ** IND-CCA2 **. In other words, what do you mean ...

At this time, "My thoughts on Saikyo no Ango", which is not IND-CCA2, is paid in advance.

How to prove the security of cryptography

1. Show that the correct answer rate of the enemy is not much different from the coin throw when the enemy A, the ciphertext C, the plaintext M, and N are given. (Definition of indistinguishability)
2. If there is an enemy that gives a significant percentage of correct answers, show that you can solve a problem that you assume is difficult (such as prime factorization).
3. That is not possible from reductio ad absurdum → There is no such enemy A → Cryptography can show security.

Random oracle model

Oracle is God. If you ask God for the answer, he will tell you anything. You can assume infinite abilities, but you can only do what you have decided. You may assume an oracle that solves the Turing machine halting problem. Enemies who can only calculate polynomial time will not be able to calculate exponential time by reversing Oracle's infinite capabilities.

Random oracle is an idealized hash function.

• Returns a sequence of random numbers for the input.
• Returns the same output for the same input.

It is known that the actual hash function is different from the random oracle model.

RSA-OAEP

Since plain RSA is not IND-CCA2, use a hash function to construct RSA-OAEP. RSA-OAEP is IND-CCA2 safe under the assumption of a random oracle model.

Try using RCA-OAEP

Use pycrypto, Python's encryption library.

import Crypto.PublicKey.RSA as RSA

rsa_fact = RSA.RSAImplementation()
rsa_key = rsa_fact.generate(bits=9216) #Bit number
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}")

With 9000 bits, it should take about 1 minute to generate.

e = 65537
d = 102445271422768774786728610671465418998417715786077416631461030523155312720317584206733543962016329891769320473707504998756121076259060083969863380925640308316956135700719982978400489398984327886291309203080000645227369518041115358572055274171020795292822605206803127875626293733879438095921088687840845348021496477808183021306161006291717320107484734865570324271064128590508767112823564702898526589701620137390590193440101544399443905230463577995724415752676335318302825910706724853701231412225971901752896977961830660932961920499134366427793856141876178470280023595127879157072726140385964752302603833364965084298489799589677327061417925446545287662381095961467077577574332292822566222369504194623196129162775804060843864512980860460412158051445085839435978300363144254661228382006364485388422008673577922004319749667871032906057672581791568891221739787764270861892177252375354647593699686978654199672072070551760804033194502882260225727231165216189279820957693900926562722774411616671287745571015351162526967907564542172052941939808771376190010179023277907550368202641303975229212168662291092494906945723622165081198214606312481691045182524064499317804734690637585388568303150949397022672704194684560914236033533318164422613648552663642476548511856266594700309835602457661190094454621087507497670637322650753423601307675188587499346800589124167673891608209932499387573048791657594194926986621689627694660445147906239669408458726594195554596144720085255734149395272271705781359507024900551613535838221119841620475338551394740443485479306218023634922739525397572539049357108887023095806284234661055646695492476785578712177291918488515599067118656065645108547095088530352973534387517758258917226608698738798789868585116840794894205029446665980628721126106856693473999320389911453477884386480815867197630855767083530063351999845567909610097599989658231081876922003349351111742065400494700687440853003964276424579852574391748872349896629839124657477496619678547054176074641671688018779623012766757021377865901385330119901021836273253907010798517858174168928355539158173347683078303051910516462386700745831889290632345880991778719606269518796628640101558412793534057953855010217768848505978463139475986236828422001147839704485486529482276542347526188855967625387674503254159443164312245392229620593904153714031063117891168880551490417553050530329980965850844213245287232106049233838415932292353248684204163389491222421722829543765255704314037087356674730743927818534613389923977154818103457335165532130572792557594083798993422048388831910357486159560623515345150976914924948633104886062664822302310928197107632431941182253377522502540522888437707317503443131624017839551631795463671297252309402434544410149945179036261740849312764702419104218920959616895608613180302844504923633
p = 9914461832686194098465923493437221453740210898452375516850385827081073195688425335861654781598045849864315026494670689193243841245509538836094571301959178485645659587800910077499048912365176587744252297552682256313170221627873706028766767715369634222023495913682543363062775318991207077738787499140674237860971675255810171058122929206010255198969821059609815401642987851715298751215008531907749963869827842519855710621233576239834912079805599229986723536952226397841333773045305668714935255184317474719921683383986501166747550329006518864508658430076912132968876866003163402605715951997297270274301081852818952931301570871164078792380667973483652839445017084147128272971028471016728223116298126619476871704129721059801452768908286362796778359456835522990643100144308946028127417502632410902975766543634371912503377053200213610307048761980816386267680452602811989917214683662537702962510846569696896766375441610645800737478195464441955570648610142660595997389962294586005023425553976456941137204858225512975707546515981687692729432786839584216504531114871471540508293571969028691523644935014613644456225447902549666210894819814778192548293452205396686168787805202073961355619931602916130081968436007538429654027932452056495821569850340965283215721661700935856640142695890369871947885718868336217009242566365550232374430051958649977503257884214765953249944184899624212764341537740196597881
q = 13808048414262925640480534390436067815119988400934773814488378440341749311980439647613071059125596499249292985551633600588792052049707443486548748639756137725160809138953933498320259931713345166343103529407375661430472534743616248511458723626960540573526883796013429641562024721050812589030283092301462036056001883178796641287105446591725726485955568224550746834289076376111745769065307970507477031499711579212918673770778036683212227410130480417520092178104094156645812562802533878664008552102263537732655673242851625896631829834015790621370047286516520312587373204326398152995666388062104497504582411226322500417829081377360929557334941872133341103528318878995956338178614078626610695172511476230640194277967728056885512980245349261379972413784544142617072645551997326887817274093582920893688142645587622109461424745534470038551725109411292072041102083112309659257776303138631106458773407330074649230153748006574041623678807946298814812123907597946162820014788698550701120296807129278775942570876844470181017049112544833584673138575398590829765799314313051068302881271428326449095224019645896898388592808924678887498669570701223057815567790401250951256627893778627130586492552344913055120859508422669992038818987496103490886239592525439928759446508699356737374967464208681380505166600196494395364992549550431449366105848455027463482227639300852033113420145671558939847080982502534046039
n = 136899368987092902008397385102376061107585217859269531916401149142508201573138949822741191824290198644391369938326952982147909120053626832027668299160403908532682630863081082406366512524544499657114644928781966892038947782636881456165748149651248697288210653455911273608566368542651484095434218733255010533068629869015249692460532061035015761839288523721731589457266680167122179929309339965619165571218626082094633474858469810478689215934769314909483331671862426600240856018391750642028782967254318058136321376030921763056165515644470545696191626735112841963312642096810876502601293825061170237784306576417423826635200252751843952931593633749775472901932383541518012013977305945287044481688114438411606237728948838177426428819346831392737630288064689979387796624816984789220335715016436785655465880603557618302247077747757353415661800623796954721856313041019248811773904952570675071658509805385479279079758319999811345429999554174799429347420607931272492131927173810432154255703497219211430478997769978776553838381788581455657966598887658782728721674910763293989529206951106959700607179365466454516214678993720323653253010432761069114573499318549336129334846918424962453573412792932133692369981746774097600805149148157179246066323128599741797719548590505144809130878940486261880701023030854800458268061868453447528139773282809666189765945603030617556916059932189022130852005355685087591584799977483315782156857141535591765178208313501287401387035530783080613608313563694213909678539679110882894073221793096157263369025956185819665213134572433650909275071804615831013560372672717232190853909252882206712863287139409871186025364524272181744881818556474803489685888693203811213504041020480388718879154793050039316303335808099902957227102965006452682711768405093335276184196887544703149433006649574649368620743670511304258768061065068169663228789511843901150543106790349312764630648225190420501693666463528516803764140438044474643948056601118577984717857149094582828556491199452942490955690649812925171923467409361474462256557933599062772214422930500001770031242968198751400968039084812626425966241812531382953883355581708999749247293358123204433872105132590742663748784367779156234749355355046653439979809098946593385742135673592844193886902875617326633648825479634476718151325781937037338679534814532019547853353311899893858992829559421871620392674668391476473357318375430596525718485947631285582331036675282573848490238288808934248666057220950811261459437894137385378527142259531650441429394541791020355783374048234124828283254127603016315902883209626120931168089158976607167132867254604228347605847781515415388949296736457798321063075691138053833482988399954754556710444668213590390691723876949212458976776693156769945727067618010294919528044772844545049348612282441623843359
u = 6182427760841655203629142226614051369143167991253318003343351463497953639001088445627407802912670145659615421205327223873760604813620139579037470841633898546076180437056012654831482468520835198750620772722618925878843014331831472271447618463082723935506561741376188006970426975622351119189528010877478143494468748282915176736242570576275789487474089551608317206852486630342559072144567146000221050236466006219835406833976655424990322892006876818454414635771187292417480975202645955139329122918007553272552458658282734198403244269618996757611229531201156517751378508782310383516409819635845744124191257939679736851452672498095341060658527746185251921571202394055102812430289062880282584673172537229462333047128806163773061515088348058802521080818496312379833062110354857110453478511283408666626033422633005257909449908970617508672278293478825270355004217821984474117178285645281610582885544953295691233244858368154940434530637994237054976155160879734315197816179073452609044716652848760793107827747628843618205784367818892338709013601614673365062867800853380752479875669492082742054572397834254879441391015064402281751174073187148768497278740742648441929966246520924331776589685338461055072186009869437031130346256626552532987608884480214525768671798824496114097328796988645597280779172026594614862996915452996252700061846281536218191001841037840600844264563423716195505729460233228290944

Encryption phase

• Use SHA512 for hash function

from Crypto.Cipher import PKCS1_OAEP
from Crypto.PublicKey import RSA

from Crypto.Hash import SHA512

message = u'The plaintext of the TEST string. * If the character string becomes long, it needs to be divided!'.encode('utf-8')
P = binascii.b2a_hex(message)
key = rsa_key
cipher = PKCS1_OAEP.new(key, hashAlgo=SHA512)
ciphertext = cipher.encrypt(P)
ciphertext

Wall time: 13 ms

b'0Cn\x8f9g\xf3\x88E\x0c%F\xe2f\xa0\xe4\xb5\x93\x12\x88\xfb\xf9{\xd62\xf5\x02\xd26`4>\x1e\xa0{\x10\x1f\x05\x9cdA}2\xe3+\x11[\xe1W\xccw\xd7\xc4E\x93Zb\x00o\x1b\xe5\x07T#Kh\xd2\xcc:\xe0\xe3E\xb6\xbc\xa6\xcb\x17\xc6C\r\xf20tj>v#\x03\xdfP,Ba\xf9\xf7G\x83UY\xad`\xd3\x8d\x7fJ\xdb\x8ej\xd3\xbc\x01\xbb%\x13i\xf3\xc7\x8f\x86\x13n\xb0j\xf0f\x84\xc4u\xe0\xc1dq#:\x1f\x85\xec3*\xe6Q5h^\xb28-\xc3\xb1J\xef\xfcJ\xbb\xfcr.B\x98\xad\x8b\x80\x1e\x84\x94\xd4\x05\x83\x92\xa1\xedc\xb8\x13\x1e:\x8fJ\x8f\x8b\xb3\xc4\xc4iq\xfb=t\x81+\x96+\x0f\xd8\xa3[\x08_\xdd\x8fAE\xd2\x9f\x92\xe4\x9a\xd0,\xe7\xfd>\xc0\x89\xfa\x96s\x07\xdb/\xa5\x19\xe9\xe1\x863v\xa0l\xf8\xaf\x97\x1d\xbe\xbc\xd4k\x8a\xadmE\rb2\x9d\x84\xf3\xd2\xeb!\xce\xa1g\x97\xf8=\x9d\x10k*\xaf\xda\x87 \x1d)\xbc\xcc]|\x82\x01.zd+\x020\xc4|\xb1\'\x7f\xf4\xa7H\xe4\xd1\x8a\xcdK\xd9\x0c\xa1\xf1J@\xc6\xf7kZj\x1c}\xd5\xd6*\xce\x86\xc8\xf1y\x05\xce8\x9f\xb3^)+\xeb(0]\xb8u\x80\xf6\xb6\x97\x9a\xc4\xfaS\xe7\xf6\x98946\x14/\xa0\xde;\x03\x9eD\xef\xc6\x9b\x8c_\x82\xc6}\x17\x07\x87t\xc0[w\xce\x13%z\x97\xa3\xe2\xae\xea\xe1\xbd\xce\xa0N[g\xd32\xfc\xa8~N\xbb\xd2\x08\xa6B\x90\xfc\x10C\x01"~\xe6\xc1\xf5)\x0e\x0f,=\x11l<S-[\x00\xd0\xb4\x8a\x9b?\x97\x00\xd6\x97\x0f\x91\x8b \xb9_AC\xa7Cb=7\xbe\x85r\xcd\x0f\xac\xae\xec\xc0\xda\xf5Y\xa9\x0f\x95{R6\xdc\x9a\xc3\xfc\xafwts(\xd03b\x14\xe0\xc8m\x14\x17\xad\t\xa8\xfa\x1a\xea\x92\x88\xea\xf3\x08OoIG\x08\x8c\xbf\x1e\xa2\x86\x02\x08\x06\xc9\xbf\xe8\xa0\x95\xcbL\xa2\x18\xe3\xc2\xadC\x02\xf4\x15do\r\xab\x1es\xf9\x12\xab8*\xfd\x0bqT\x1eC\xa3\xc9~\x8c<\xa8[\xbb\x0c\x9d\xe2\xe0\xf4\x14\xf7\xc2\x1ab\xb2/\xb0\xde\x7fd_`c#\xd1|\xd9m/&,\x9ai\xae}\xc5\xc4\xad\n\xcfn\xcc\x93\xfa\xfeQ\x06/\xe40Bl9\xe4i\xd6\xbc\xdbq\x85h=l\xf0\xef\xe0\x15\xeb\x97\x05\xd7=\xf2\x8b\xeb\x06\xa4f$\x99\xcd\x7fDJ\xa4\x93\xcd\'S\x12\xc1\x8fD\x16\xc7\x94\xc8\xbc\xc8\xf3g\xc3\x83\x9f\x1f\xcc\xbc\xe5\xe7\x96\x9c\xee\xca\xf42b\xc0\xf2\xde\xbd\xf9\x85\x8aZ\xbbF\xdaqsA\x92=\\\x8b\xdaR"/\xff\xee3\x0f\xd0v87?!!\xa3\x92\x18D\x16\x02\xce4\xf9\x05/\xec\x8css\x867\xfa=1\xaa$c\x1f\x08\xaa\xcd\xf1\xd6\x91\xcel\x91\xcf\x95O\x8d\xb1[gJ\x9b\xa9\x8b\xe6\xa0\x10\xfd\xd6D\x8b0b7\xdd\xa5vev\xd3\xf8\xb4\xa9\x7fv\xfb\x1d\xfa\xa5Q\x88G\x0bb%/c\xf1\x16g\xae}\xdfO[\xacz\xa0\xd6\x8e\x88\xea\xc4\xd6\x13 P\x15\xb42\x9a\xed\x90\xc1\x0f\xbc\x1f\x98\xd5ZTu\xa0Th\xcb\x01\x12\xe6\xa9\x9e\xf1(\x9d/:\xe2\x93\xa1\xa0\xa1\xfa\x07\x8b0\xfc\x12\xf4\x97\xa2\xe3\x93>\xc1\xf9\x8b\xb6z\xa3\xebf\xc6\xda\x8e+\x86\xd9\x883\xa7\xe7\\Cos\xc0\xf7p\x16r}\xe9\xe9\xf6z\xab\xc16\x94\xbfR\x8c\x10Wz\x9e\xb1\x85\x8a~&\xf5\x05&\xb0\x93\x98t\x9a\xc29\x81}\xf5\x1c\xe6\x9al\x05\xfd\x8c\x08\n\xa8&\xdc\xc51\xce \x9fy\xe8\xaf\x82\x1a1C\x9f\xd4Z\x92\xb07\xe7c\x01\x03\xe4\x17\xa3\x1d(w\x1a\x93\xd3k4y\x80\x06\x05wE[\xa0\x9bV\x0b\xc1/\x97\x07\x1cw\x84\x97\xf9\xd6t\x02\xe3\xac\x81\x0b\x84\xd8*\xcdoTK\x98z\xe5\xec-Ih\x91\xcab1\xa4\xc5J\xf7\x9eT\x11\x16\xb7\xa08\x98\x07\xdb\xea\xcf\xac\xe6\xcf\x87\x8aP#\xb3\x0b\xc3\x83\x1b\x84]\xf28\x11\xaf\xda\\n\xe4\x18D\x16\x00\x9b>\xf7Q\xabB\x1c A\xfbh*\x11\xba\x87\xa8\xdc\x8a\x82\x85\x80\xd75\xd2wD\xc68\xb8\xe9\xf5\xcah\xd0\xf4xl\xfd\xe4\xe4&\x84\xed\xf8\xc6%\x80\xab\xb1\x0b\xfeJO\x7f\xa4\xe3\xd7\ni\x99\xaf\x04\x92\xf4\xe7\xd2\xb8/M\xe3AV40s_V\x93x\x0eh\x8bI\xb2Y\x9f\x19\xe9\x1e\xb3\xd4\x05\xecG%\xe7c\x91\xf8l/\x18\x88u\xeb[\x01\xa0\xfd\xd6-\x87^kR\x02v\xe35\xfa\xac\xf5\xa4\x9d\xef_qO4\xa6\x94\x81\x90\xa5\x8c\x0f'

Decryption phase

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

Wall time: 739 ms Decryption takes a little longer.

'The plaintext of the TEST string. * If the character string becomes long, it needs to be divided!'