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

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

safety

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.

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

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!'

Recommended Posts

Ciphertext in Python: IND-CCA2 and RSA-OAEP
Stack and Queue in Python
Unittest and CI in Python
MIDI packages in Python midi and pretty_midi
Difference between list () and [] in Python
Difference between == and is in python
View photos in Python and html
Sorting algorithm and implementation in Python
Manipulate files and folders in Python
About dtypes in Python and Cython
Assignments and changes in Python objects
Check and move directories in Python
Hashing data in R and Python
Function synthesis and application in Python
Export and output files in Python
Reverse Hiragana and Katakana in Python2.7
Reading and writing text in Python
[GUI in Python] PyQt5-Menu and Toolbar-
Create and read messagepacks in Python
Notes using cChardet and python3-chardet in Python 3.3.1.
Modules and packages in Python are "namespaces"
Avoid nested loops in PHP and Python
Differences between Ruby and Python in scope
AM modulation and demodulation in Python Part 2
difference between statements (statements) and expressions (expressions) in Python
Eigenvalues and eigenvectors: Linear algebra in Python <7>
Implementation module "deque" in queue and Python
Line graphs and scale lines in python
Implement FIR filters in Python and C
Differences in syntax between Python and Java
Search and play YouTube videos in Python
Difference between @classmethod and @staticmethod in Python
Difference between append and + = in Python list
Difference between nonlocal and global in Python
Dealing with "years and months" in Python
Read and write JSON files in Python
Easily graph data in shell and Python
Private methods and fields in python [encryption]
Find and check inverse matrix in Python
Linear Independence and Basis: Linear Algebra in Python <6>
Call sudo in Python and autofill password
Differences in multithreading between Python and Jython
Module import and exception handling in python
How to use is and == in Python
Project Euler # 1 "Multiples of 3 and 5" in Python
Quadtree in Python --2
Python in optimization
CURL in python
Geocoding in python
SendKeys in Python
Meta-analysis in Python
Unittest in python
Epoch in Python
Discord in Python
Sudoku in Python
DCI in Python
quicksort in python
nCr in python
N-Gram in Python
Programming in python
Plink in Python