Pythonで暗号：IND-CCA2とRSA-OAEP

暗号理論復習

適当な暗号を考えたとしてそれが安全なのかどうかはどうやって評価するのだろうか。
まず暗号を破る敵を考え、次に暗号がどの程度破られたのかを考えるのが暗号理論の教えるところ。

攻撃モデル

• CPA(任意の平文に対する暗号文が得られる)
• CCA1(任意の暗号文に対する平文が得られる)
• CCA2(攻撃対象の暗号文を見た後でもそれ以外の任意の暗号文に対する平文が得られる)

敵の攻撃能力は下の方が強い。

安全性

• OW(一方向性：暗号文から平文を求めるのが困難)
• SS(強秘匿性：暗号文から平文のどんな部分情報も漏れない)
• IND(識別不可能性：暗号文が平文AとBのどちらのものかを区別できない)
• NM(頑強性：暗号文が与えられた時、ある関係性を持った別の暗号文の生成が不可)

下に行くほど厳しい条件になる。

IND-CCA2とは

我々が求める暗号は敵の攻撃能力が高くても厳しい安全基準が保たれるものである。
よってNM-CCA2の条件を検証したい。
しかしNMの条件は理論的に扱うのは難しい。
ところが幸運なことにCCA2ならばINDとNMは等価であることは証明されている。
だからIND-CCA2かどうかを考えればいい。
つまりどういうことだってばよ・・・。

今時IND-CCA2じゃない『ぼくのかんがえたさいきょうのあんごう』は門前払いだってこと。

暗号の安全性をどうやって証明するのか

1. 敵A, 暗号文C, 平文M, Nを与えたときに敵の正答率がコイン投げと大差ないことを示す。( 識別不可能性の定義)
2. 有意な正答率を出す敵が存在するなら、難しいと仮定した問題(素因数分解など)が解けることを示す。
3. 背理法よりそういうことはありえない→そんな敵Aはいない→暗号は安全が示せる。

ランダムオラクルモデル

オラクルとは神様のこと。
神様に答えを聞けば何でも教えてくれる。
無限の能力を仮定してもいいが定められたことしかできない。
チューリングマシンの停止問題を解くオラクルを仮定してもよい。
多項式時間の計算しかできない敵がオラクルの無限の能力を逆用して指数時間の計算ができるようにはならない。

ランダムオラクルとはハッシュ関数を理想化したもの。

• 入力に対して乱数列を返す。
• 同じ入力に対しては同じ出力を返す。

現実のハッシュ関数はランダムオラクルモデルとは差があることがわかっている。

RSA-OAEP

素のRSAはIND-CCA2でないので、ハッシュ関数を用いてRSA-OAEPを構成する。
RSA-OAEPならばランダムオラクルモデルの仮定のもとでIND-CCA2安全になる。

RCA-OAEPを使ってみる

Pythonの暗号化ライブラリであるpycryptoを使う。

import Crypto.PublicKey.RSA as RSA

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}")

9000ビットだと生成に1分ほどかかるはず。

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

暗号化フェーズ

• ハッシュ関数にはSHA512を使用

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

from Crypto.Hash import SHA512

message = u'TEST文字列の平文です。※文字列が長くなると分割する必要があります！'.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'

復号化フェーズ

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

Wall time: 739 ms
復号化の方がやや時間がかかる。

'TEST文字列の平文です。※文字列が長くなると分割する必要があります！'