publicKeyCryptography

学校关于公钥密码学的部分实验

1 rsa

1.1 运行结果

n = 10 的示例

p = 17977, len(p) = 15
q = 23, len(q) = 5
n = 413471, len(n) = 19
phiN = 395472, len(phiN) = 19
e = 491, len(e) = 9
gcd(e, phiN) = 1
d = 180419, len(d) = 18
e * d mod phiN = 1
e * d - 1 = 88585728
(e * d - 1) / phi_N = 224

n = 1024 的示例

p = 3828281911187973009199499145938687251826186747748746884223212089985541092642931283863902965847605791753152803524761759267647713539818562237054218812986360569990779142705539322536418452533501028196928107637812460700693407366269984526425010696152772057857725365935872098205520243162057340482187491446438150927387, len(p) = 1029
q = 3886258568146491055175613596261941209610177424189010183513868748218090979073006322681272411980832069178667294924286428248610978694956790054995287969130774131510033077760327631364588608769279248823275786407140265663627488272189568724261749268117102491514102100086332230839398043719245083249812281450830310783, len(q) = 1019
n = 14877693378634484222233937200570322437083853754386056072786037865896309320764489934047143952759595011941396887064215029343581165723113484164528947879757953795839158413249993774587129371708010626197995030433731444730630381867753520527178890380189787436853306978515404050355302849167930411516866915393641975025141353007171613574406934924350551002225579055363555292414405600584078557310281965811990180854474856864897500761532930789402838951677544404860601523965859304274013327838816696444418923740605963265858437861842503770061595756735739881679392777074704452696144742548698008549419372929727441186677620728740876114021, len(n) = 2047
phiN = 14877693378634484222233937200570322437083853754386056072786037865896309320764489934047143952759595011941396887064215029343581165723113484164528947879757953795839158413249993774587129371708010626197995030433731444730630381867753520527178890380189787436853306978515404050355302849167930411516866915393641975021309184837415494074152260164815601809189782130190619398007679641850319373688277675625405942594888233042566029941846885093506514433164025377751387423010367960151724152055517046276635882598335655820107054437622902803704560902193565786530120331653815292346905274512739578113059731723950855621240317000851894875852, len(phiN) = 2047
e = 112745749727580707611018538211800349708436743360028736057947264101165383946090786265033963027012044144486885567897819060337111993487051561101533394070878120285124115041197631497184147378339978501394348072307128181487834747723744179881642370432914784416159842908937453007973277936430645041461195462557877808941, len(e) = 1024
gcd(e, phiN) = 1
d = 1618620896693938008007363000833465298309719260188849347988446922948461647016558967193414463892768748047805597092999915755971526737331110303704456248570482546119612523893351542691456783125587733021700948131755768781349294414410518105015613814332308570661932472956833562121627420027451274399747365627959583850575750298707391247292498234258922877758227514908991056067028857910274252579006253998712134775415659960626098501126166760398995200836706877741080860544678141525463938451247843744414878465041531815053916549936019777485730170429838939305756965431880091592802171094639189381089149205411604002083345386456599458005, len(d) = 2044
e * d mod phiN = 1
e * d - 1 = 182492626522487001842914891741029009755942770047093117510336725207716797379791126133025806377073163670600202433899385893110990756092677932465998172436168151060575368714702236848574989361005433509325948287966100661812925617772538812801369385537455218502804512141724806720287748557293145378370117426093657835169454072170842986512790452951128694833295727825980746742225125197807440173221944767825693966979062995252507948453596190423754710583664266878381131974989076130138866523990944055184134993589616888450520848526915179319006631627001223723527605864895185478450335482834657179345594048015128693611257658681398285241553575920323990650835922051820348189502061909501391219531618334170043278159165655403339261216338400469556109275857050902354469138856249957264297912310173151669568765085735670238406970044570889277131737235554059432804037082962091106303370804573877424870693794351011331275322414744164456652314174731477543022704
(e * d - 1) / phi_N = 12266190858897555730768082103452744553613386725312016634331397334169421784380179076676064625471079493938960537070532577130656772208890617126224606594497432067268462047402723454244691703486827370513171465341856242651661700200992578645934087568503269335402197838120203194592339065773054479724434958855683579252

1.2 实验遇到的问题

1. 一开始不知道不能调库，去网上了解了一下 RSA 相关的库，还涉及到 Base64 编码，写好了才听老师说不可以用。解决办法是自己写一个。
2. 指导书上介绍的编码方式是不对的。解决办法是自己设计编码。
3. py 不太熟悉，开始写实验的时候比较头疼。解决办法是用熟悉的 Java 写。

1.3 字符分组方式

• 从文件读入待加密的明文

就算是可打印的 ASCII 编码，十进制表示编码的话也达到了三位数，如 z 编码是 122。

故而如果一次读入两个字符的话，需要将其转化为最高为 6 位的十进制数。

• 每次读入两个 byte, 如 a, b；
• ascii 码为 97 98；
• 将其组合为 097098 的 最高为 6 位的十进制数。

如果最后没有读满两个字符的话，就用 000 补足。

（from in file）明文字符序列 -> 明文编码序列，其中的元素是最高为 6 位的十进制数；映射是 ASCII。

• 加密

明文分组的长度是远小于 nLength 的，但密文分组长度 <= nLength，并且这个分组长度不是固定的。

明文编码序列 -> 密文编码序列

• 写入密文文件

上面说到，密文分组长度 <= nLength 且不固定。考虑到之后读入密文文件，我们需要在写入密文文件时对密文分组补充长度至 nLength。补充的方法是在密文分组前补充相应数量的 0。

写入密文文件的是所有补充完前导 0 的十进制密文分组的字符串，这里就不需要再转化成 UTF-8 或者 ASCII 了。

密文编码序列 -> 补充完前导 0 的十进制密文分组的字符串序列 -> 密文字符序列（to en file）

• 读入密文文件

一次读入 nLength 长度的字符数组，去掉前导 0，重新变为十进制密文分组，直到读完。

（from en file）密文字符序列 -> 密文编码序列

• 解密

密文编码序列 -> 明文编码序列

• 写入解密文件

按照最开始的编码方式解码。

把每一个解密明文分组，也就是最高为 6 位的十进制数，重新拆分为两个十进制数，转换为两个字符。最后如果有 000 就忽略。

解密得到的明文编码序列 -> 明文字符序列（to de file）

1.4 算法

大致复习 RSA

参数：

需要两个大素数 p，q

得到大素数乘积 n，其欧拉函数值 phi_n

找到一个小于 phi_n 的，且和 phi_n 互素（最大公因数为 1）的 e

求出 e 的逆元 d（模 phi_N 意义下）

加密：

c = m^e mod n

解密：

d = c^d mod n

所以需要以下算法：

生成大素数（参数是素数长度）：Miller-Rabin 算法

求最大公因数：欧几里得算法

求模逆元：拓展欧几里得算法

快速模幂：用到了同余性质，以及平方求幂。还可以用 CRT(Chinese Remainder Theorem)

1.5 java 实现

很幸运的是 java 里 BigInteger 类包含了上面提到的所有算法。（乐）

当然也可以自己实现。我个人的实现放在 SelfUtils.java 中。虽然并未实际使用，但是结合标准实现做了自动化测试。

1.6 更多

想要补充更多攻击部分代码。

2 ELGamal

2.1 运行结果

• 公钥和私钥相同，选取的随机值 k1 和 k2 不同，用学号作为消息 m , 打印输出内容包括公钥（y,p,g），私钥 x，签名结果 (r,s) 以及验证结果。

m = 200111407

test 1

ELGamalUtils init...
ELGamalUtils param start display
ELGamalUtils pubKey start display
len(p) = 1025, p = 246447862447654194306480131872934494863228912340037457463305306510496335260722258477771354345967469426048085697933107846361385853634938173309452231275393821477882382020968571475959996993461145174561427801934239239758597527517900379681301630026881100612456008448212363582648860465937747419599539166598117543247
len(g) = 1025, g = 200686197793119782047164364515539652461822786372344388628075628846207316230771920712374397734581152795459223993455321014759682078016082466931337610233007508542745838163078610976785230305055755564544458859949064676338591706791417232726248595462331865514078524529357844780232721802850901633900202629302246993968
len(y) = 1022, y = 44866483419346699457498801734363200687352831127016603830568241640804918113378601138622873015125362526559628117740420991035695674094888726717448037807469522100807988161648000957137552359415962064675523536221899915605014936822545049715984498588635956839733917739734641464840926883575985479550923872258630290193
ELGamalUtils pubKey end display
ELGamalUtils priKey start display
len(x) = 1023, x = 75383904813064178046021950503082862527311357784924552113449063442285081231944597923799328947591223103997146496567320253405134265876034620485808205246131399105997316780240949442239047676285819716933007626423082889795982591817185790219198744531699858679834238639045763099903572673770188848463836037350557583350
ELGamalUtils priKey start display
ELGamalUtils param end display
ELGamalUtils success!

Signature gen...
len(k) = 1025, k = 227325146014117735637763034576073252724486160272481613795087775245846445739744864128503561908094605385995966010266011157994649990244423541334123812607915570993742235614559957322949308011021843007265354571559575326708068049298976788963473967175872953166332586901093141513862802643331629707756087371371085141047
Signature gen complete.
Signature start display
len(m) = 28, m = 200111407
len(r) = 1024, r = 178476778444960674874280463819851064774936197250400500559981598618383728345108179309977313017369497218026748839569301310776064557564698973075356273141040987582991549826422707798589180511902163176777186552619218683774544004348426565723640682507492190733663782979864617295761131351170206955099664914850014507827
len(s) = 1025, s = 210744163802614026786269756005554644598172304665843791948665123852373307843015751819894116931599999203262932173999646244732848456657540467449313476513243473890119409426814401277417158753748438718209446589541560870196485108410356520689659583633232852470620015066926644097407282634727213098568226849210302812823
Signature end display

verify the signature: true

test 2

ELGamalUtils init...
ELGamalUtils param start display
ELGamalUtils pubKey start display
len(p) = 1025, p = 203054175936109929857324621730239969769344205987425936107430824240245436577953153783038611643695576534307973606455261631690491206169796363806107829461639471400215666954710200674906463936467763520882875085151972602937038995852296768819854246769083177950664104188813494937465448604186102074520588941877055768807
len(g) = 1024, g = 97408722194636617926171838393363396772740779629723093367502097516619571257985434906015948883447357713768699841335707060721030145064564499881089286186758028159870826388130999306771635943288822181833588511636558863470835581593321166102977226725973145529645450942362662602555592120628422549956621373246778975425
len(y) = 1025, y = 186257284374509610648308519212846183814752928489670897811419266777775036768078818057301539599864493629332502224278263439079056656786065123651360108536587500900331482063631969721509127821987159007089828826763905305968131153294393879695595795580786840032443255443536103591636549093458963166819143819107416973720
ELGamalUtils pubKey end display
ELGamalUtils priKey start display
len(x) = 1024, x = 141232526116887923616602516174062715543477515832714873303111833725501424996402701036901280067883007499992814610756286373573254993779231779767279125303473377048433722006374098298448032012260413781474341407929871151024008216780885144504398161697243760202425604376517095069674562585867080762371377212257736370375
ELGamalUtils priKey start display
ELGamalUtils param end display
ELGamalUtils success!

Signature gen...
len(k) = 1024, k = 116205828374094956888344242661041825465401641513493713507661895913654840385089586123433726290425519144847715020537216935062899286505611102829956583549939619527161618605423518109949385485405808853630175495028094862119602409607025216985372305426781006934810687936437986617419764815253355330669155410393887715151
Signature gen complete.
Signature start display
len(m) = 28, m = 200111407
len(r) = 1024, r = 157559795726317217162555063244639366974193332781814920902170711757358875827245824271470400124613923433722907234181936211666710327809286035367920755813708385629544854564429351836217830578465108979647261293858446766872082973364423741080749511916888903081607887175758506422763750242944623350339778789689467973383
len(s) = 1023, s = 54786928930156298106626627127759448792016833980116370623362950647460921249235260033720680731854371719320216556447072633283503588708714660479780848927711436210044588903020376386531549095221629444033014462479033977723712818478318725586201037973680488608565581852027984085083115592204927773188952395229266751452
Signature end display

verify the signature: true

• 假设收到的消息 m 被篡改了，打印输出发送时的消息 m 和接收后被篡改的消息 m’ 以及验证签名失败的结果，并截图，公钥、私钥以及 k 都可以用上面 1 中用到的值。

test change m

ELGamalUtils init...
ELGamalUtils param start display
ELGamalUtils pubKey start display
len(p) = 1025, p = 184624424972597461463649467440815843410874469843972308624441862027975300623365157077579012993249954257402280654350796745552975130151637388682383355934960098383026636120053225357181020049147019337420939960501189490502631593420792618816396998738451475967481410201404526145822794831497522718949430252443523704499
len(g) = 1021, g = 16686871033234686840818482223072784962329105296725285559855928328828490591524067017365671811023014313927304143355560044908401845956034403100535441619659230094389737879793421900803257235881829505751332475805239920052421329118670501283916878381350919138022888859584381320563388370703171047653796703760492252894
len(y) = 1024, y = 108140162603091326651708724600010522514199964778946688926572811695856510428511325274579690362145858415630750320652938480681191575630293272669712757159564377461712164369392784166580368383935447685264921794024576182814612545201980245653514844666464859096565416875713552140358160905593031356437377690584641666439
ELGamalUtils pubKey end display
ELGamalUtils priKey start display
len(x) = 1022, x = 38592517295054685654679018401855853508394064587639771996154501116957633806348993467726824026854308648596123563523855598303927001692537991478164424992199360895926681350737650499872129793403245041247056231101258714897819795559907043805522337152859897209334972003223657511265273340495876128350551007173549164323
ELGamalUtils priKey start display
ELGamalUtils param end display
ELGamalUtils success!

Signature gen...
len(k) = 1024, k = 144839261329718229232936602159998281158138046846830353501986254011886422238629519931497450837842510126595490758391282241399151173419539851141414841144591280406545615160343367534921151587415111450080927484492818853072002639010644329232916255027508431349682935932845272624221405045452266586177719462710488836717
Signature gen complete.
Signature start display
len(m) = 28, m = 200111407
len(r) = 1023, r = 48026771041321504580568497041229418163129565660100934720111897032046764528632668765732599812490586343203538640177249855880694101750515946647385705672822517211404613269465548013451275102147592749268153411095468760942943159072513720914152367154649520731425101509067810298385117699691093860212788795882426296761
len(s) = 1020, s = 9223872049250989978451652849159035843608289459452664049652352162531540263698199021325144420828978176981705474931018552998985240139140797806892922310376001614513126222297300330207314308913626983715719749760627184821346122102100030823071035105035929783140551045258452734772792562003553518992525214846551597946
Signature end display


Signature is changed by attacker.

verify the signature: false

the m has been changed!

2.2 思考

• 用 ElGamal 方案计算一个签名时，使用的随机数 k 能不能泄露？请给出你的思考并分析原因。

不能泄露。

可计算 $k^{-1} mod (p – 1)$

则 $s = k^{-1} (m – xr) mod (p – 1)$，其中唯一的未知数就是 x，那么可以被计算出来。也就是说密钥被破解。

• 如果采用相同的 k 值来签名不同的两份消息，这样是否安全？请给出你的思考并分析原因。

不安全。

考虑 $s = k^{-1} (m – xr) mod (p – 1)$，其中未知数为 $k^{-1}$、x，那么签名两次可以解方程得到私钥 x。