New User Special Price Expires in

Let's log you in.

Sign in with Facebook


Don't have a StudySoup account? Create one here!


Create a StudySoup account

Be part of our community, it's free to join!

Sign up with Facebook


Create your account
By creating an account you agree to StudySoup's terms and conditions and privacy policy

Already have a StudySoup account? Login here

CryptographyComp Netwk Sec

by: Antonina Wuckert

CryptographyComp Netwk Sec ECE 646

Antonina Wuckert
GPA 3.94

Krzysztof Gaj

Almost Ready


These notes were just uploaded, and will be ready to view shortly.

Purchase these notes here, or revisit this page.

Either way, we'll remind you when they're ready :)

Preview These Notes for FREE

Get a free preview of these Notes, just enter your email below.

Unlock Preview
Unlock Preview

Preview these materials now for free

Why put in your email? Get access to more of this material and other relevant free materials for your school

View Preview

About this Document

Krzysztof Gaj
Class Notes
25 ?




Popular in Course


This 19 page Class Notes was uploaded by Antonina Wuckert on Monday September 28, 2015. The Class Notes belongs to ECE 646 at George Mason University taught by Krzysztof Gaj in Fall. Since its upload, it has received 46 views. For similar materials see /class/215023/ece-646-george-mason-university in ELECTRICAL AND COMPUTER ENGINEERING at George Mason University.

Similar to ECE 646 at Mason



Reviews for CryptographyComp Netwk Sec


Report this Material


What is Karma?


Karma is the currency of StudySoup.

You can buy or earn more Karma at anytime and redeem it for class notes, study guides, flashcards, and more!

Date Created: 09/28/15
ECE646 Lecture 10 RSA Implementation Ef cient encryption decryption amp key generation Ef cient encryption and decryption Number of bits vs number of decimal digits 1W 2am dig39ts logln 2 waits a 030 whims 256 bits 77D 384bit 116D 768 bits 231 D 1024 bit 308 D 2048 bits616D How to perform exponen a on ef cien y YXEmodNX X X X X X XmodN Erumes E may be m the range of 2m2 10 Prnhlems 1 huge storage necessary to store XEbefore reducuon unt of computations mfeasxble to perform s mam odulo redumon a er each muluphcauon 1 m 2 clever algonthms 03C Indra Chandaheriva Rightrtorlel t binary exp onen a on 5491133 raven s X szuaw Xmuaw Xxmuaw inmudN E en 31 32 E 311 1 XSquot xzrrruame x mudez Xsrrrua ms XernudNeL 1 8 w WK eZeAelBeA te YX quot modN 222 er XEmodN 3 Rightrtorlel t binary exponen a on Example E13mz11nn112 s X szuaw XmudN wmudw XmmudN 3 zzmud113 szmud114 47mudll5 szmud113 E en a e a e 1 o o x wmodN 1 1 x13 modN 3 9 1 1 3mod11 xlvmodN 27mod11 3 mod115 3 mod114 Le itoiright binary exponentiation marl N 1503va sz Niven E e e an e Y 12 Kg 2 Xe 2 XE 2 2 X 1 X 21ch 1 W X w 1610 YXe 22 ZeL3 2 39 23 X2 em 21 elf 21 EL3 2 We mod 7 XEmodN Le itoiright binary exponen a on Example Y 3quot mad 11 El l 2llllll1 E e 33 e e en 1 I I l 1 Y 02 X 2 1 2 1 2 X x modN 00110211100111 32mod11 3mod11 2moa11132moa1113m dll 5 32mod11 3mod1 4111100111 3mod11 32 mod 11 Im g 3mod 11 4 1Xx X XmodNX modN x Exponentiation Y XE mod N Rightrtnrle hinary Leftrtnrrighthinary expnnentiztinn expnnentiztinn E EL 1 an v 3139 En Exponentiatiun Example Y 712 mod 11 Rightrtnrleft binary Leftrtnrright binary expnn Entiztinn exp nnen ztinn 1211oo2 sum 7 s before round 1 15 computed sm 7 s a er roundx 15 computed u RightitmLe Binary Exponen a on in Hardware Le itoiRight Binary Exponen a on in Hardware Basic Operations of RSA Encryptinn 1 k El public key expulan c mu mum me mum Deerypuuu Lk We mu phmm Eilihmex privzle key mudulus mm B Time of exponen a on Luge L k modularimuluplmamons e L mama eL modularimulnplmauons 2 17 large random Lrbxt e Lonese N 7 L MMDDGQ r ume of a smgle modular mulupueauorr of two krbe numbers modu1o a krbe number SOFTWARE tmmmuuk ARE tmmuu o Em k Algorithms for Modular Mul plica on Mlltiplicztinn 2 Mlltiplicztinn enmhiued with 39 aperrazdrpenml 02 mndular reductinn aratsu Schonhagerstxassen FFI Mk Wk Montgomery algorithm 902 Mmiular Reductinn classical Barrett eomplemry same as mulupueauorr used Selberxtchell sue Pap eryandyl encil Algorithm of Multiplication 1m um um x Eli39s mm hub Du AA m D AlB A Bl Dl Al l A B A13 3me 3m 1 AHBA 6 c Classical Algorithm 1 q m 2 quot v Ell2 XMb x q39 q i quotM v ni2 Time oi basic opera ons in soitware and hardware SOFTWARE HARDWARE Mudqu 2 Multiplicatinn Em k Mudqu k7 L a k L Expnnmu39zu39nn Em 9 Time of the RSA operations as a function ofthe key sizek SOFTWARE HARDWARE Encryptinn signature veri cation ck k2 cm k with a small Expnnmt e Decryptinn 2 signature generation 59a kg in k Key Generation 5 k Mgzk 9 k34 gzk Facturiutinn m 2 ex e k n k making RSA p e 1 V w Effect of the increase in the computer speed on the speed of encryption and decryption in RSA to keep the same security computer op and speed 4 size encryptiondecryption speed 6 m Decryption using Chinese Remainder Theorem III ma til i c i an rdmodQel mad El WWII MM RuMu Rymod N where RPP mon PPmmodN Ru Q modP Q QNmodN Time or decryp on without and with Chinese Remainder Theorem SOFTWARE Without CRT tmae tmrandom e k Lk With CRT k 1 Lozccxik2 in rmdom arkZVLk22 E 3a ZEDEEGQ HARDWARE Without CRT 5100 tugrandom e k Lk eh k2 with CRT 1 tm snoozcmoandom 2 w21w2gtch lt 53 moo n Chinese Remainder Theorem Nanhr M for any r J gedn m 1 Then any number 0 s A N71 can be represented uniquely by AH2Amndnl a1Amndn1 zMAmmihM A can be reeonstruetedfrom a a2 am usmg equation A 2zlN N mndnmndN Wham N il nr in nrinri nm Chinese Remainder Theorem for N Q NP Q gedPQ MH1I andP1IQand Q MM r modP Mu V mdQ modN MF Q Q modP Mu P P monmodN MP RuMu RymodN Concealment of messages in the RSA cryptosystem BIakIey smash 1979 77mm aixlmexxagex lhal m nalclmnged by the RSA enayptian For example M1 Md M e121 mod N Every M such that MPMmodPe10elgt MQZMmonE 11 CmodPM modNmodP M modP Mmod1gtM CmonM modNmon M mon Mu monMu Concealment of messages in the RSA cryptosystem Bzakzey smash 1979 A1 12m 9 message not concealed by RSA Number of messages nnt concealed by RSA 6 1 geomeel P4 1gedee1ge1 A 23 5 9 o 9 oPL N B gedltee1Pe12 and gedltee1Qe12 C gedltee1Pe1Pe1 and gedltee1Qe1Qe1 his possible lhalall message remain uncancealed by RSA be Ef cient key generation Generation of the RSA keys e e 3 or 2 numbzr pnm gznzmzmn r 1gcde1P 12 r 2 P Q gcdeP1 1 gcdeQ1 1 Ewe101 Extended 5mm 5 algorx hm NP39Q dequotmodP1Q1 Random vs Incremental Search Random Search pnmes numbers tested forpnmahty Incremental Search starting point chosen at random Is there a sufficent amount of prime numbers to choose from 0 X v 11x prime numbers 11x the amount ofprimenumbers smaller than x Is there a su 39icent amount of prime numbers of the given bit length to choose from 11k the amount ofpn39menumbers ofthe size ofkbits 0 2kquot 2k nk prime numbers at W m e e 0 5 W e a wet Average distance between primes ol the given bit length 1 Average distance between two consecutive pnmes 2k 2M 2 Average distance me 7 e s 1 2H s M mm e o 59 kl Average distance between primes ol the given bit length 2 Number of bits Average distance Average amount k etween primes of odd numbers t n cnmpnsite Fermat s primality test Wn wimesses to the eomposrmess ofn E7 osltness ofn lunsl as Wni 39 anlslmnrln n cnmpnsite Carmichael number Fermat s test Ln Liars to the eomposrmess ofn lunsl Wn a 1 s a s n gcdz ngt1 1 Ln 1Wn C armichael num bars A composite integer is a Carmichael number iff quotPl 391 39P 39 39Pr k 2 3 p are distinct primes Rep for i sj P 1 1 quot1 Vp Smallest Carmichael number 561 3 3911 3917 Among all numbers smaller or equal to 1015 There are about 3 1013 prime n bers a 1 5 Carmichael numbers Good probabilistic primality test 11 composite Wn esses to the sompositness ofn v n composite i Wn i 2 i Ln i If as Wn tenretllrns n compositequot else e returns 11 prnhzhlyprimequot 37 in n psendnprime to the base aquot MillerRabin test n comp osite Strungwitnessesto the eompositness ofn lunsl v n composite i Ln i g qn4 lt n14 MillerRabin test n comp osite n Strungwitnessesto the eompositness ofn lunrl For certain composite numbers such as n3 5 7 2k1 there are only two strong liars 1 and n1 MillerRabin test Mathematical Basis Irh isprime than 1111 twn square mts mnt lnln h i c there are only two humbchs y and y such that y modh 1 and y modn1 y1 and 3122171271 modn Irhisummsimhch 1 has atlcast full squarernntsmndllln h i c there Existnumbers y y y y such that m h1ymodh 1y 2mouth 1 modny3 1modny t1modh MillerRabin test Algorithm 1 Find s andr such that 2 r Whererts odd F or example h49 hcl482 3 54F3 n 61 6022 15 52F15 MillerRabin test Algorithm 2 Computc an modn armodhymodhymodh zmodn s squarings square modn ax ax awe 3 a tax 5 mean square root modn MillerRabin test Algorithm 3 square modn as 20220023 ax 5a 5 mean at square root modn result aftest 1 1 1 1 1 1 x x r1 1 1 1 x x 1 1 1 1 r1 1 1 1 1 1 x x x x x x x 3 t 1 mod n prabablypnme a campaslte7 rlngz nf the hnllnd an die errnr prnhzhility nf declaring lobit camp nsite numb a a prime after 1 iteratinns nf die Mllerrthin test k numbe z rnumber oflteratlons of me MinerrRabin test ofbxtsofn 1 2 3 4 5 6 7 8 9 10 100 5 14 20 25 29 33 3s 39 41 44 150 8 20 28 34 39 43 47 51 54 57 200 11 25 34 41 47 52 57 s1 s5 69 250 14 29 39 47 54 s0 s5 70 75 79 300 19 33 44 53 s0 s7 73 78 83 88 400 37 4s 55 63 72 80 87 93 99 105 500 5s 63 70 78 85 92 99 106 113 119 600 75 82 88 95 102108115121 127 133 Minimal number nf die MillenRahin tests 1 necessary m nhtain die prnhzhility nf errnr lt z quot1quot far a lobit number n Random vs Incremental Search Random Search pnmes numbers tested forpnmahty Incremental Search starting point chosen at random Using division by small primes pnmes numbers tested DDDDDDD DDDDDDDDDD R1 D 7 Division by small pnmes R1 7 MsllerrRabm test wrm base 2 ReMruereRabrn test with are random base a 7171717171 Merten s Theorem The propornon ofcandidate oddmtegers Nor ruled out by me tnal division by all pnmes B 15113115117 11B max 112 lnB For B 561Bw0 2 80 oftested numbers drsearded by me mal division Incremental search for a prime micient implementation or division by small primes Set ofsmall primes 3 11 S2madll7 72madll9 92madllll U2madll2 y Division by small primes 7 Practical implementation 2 3 s 7 ii Sk Optimum number of small primes 357 Bum Bequot DlnagD R2 tune of the Mtllenlzabtn testwnn base 2 anne spent on test dividing one number by one small pnme RSA countermeasures against known attacks Reenvering RSArencrypted messages withnllt a private key 1 Guessing a set nf pnssihle messages 135 FBI E puhhcimjfjmmarne ofthe congress member who eommitted atax fraud Wm Emmaramamel Emmaramama Ewarmkrrrmamem B Reenvering RSArencrypted messages withnllt a private key 2 Small 2 andxma message e3 00000000000000000 1 m lt N 13 7 3m0dNm3 4 E Hastaere attaek e3 m sendto three different people Pm3N m3 mod N CRT 1 ma mod N a mzmodNN2N3m3 m3 mod N 5 Optimal Assymetric Encryption Padding 1 BellareRogaway Coding gt168 bits 000000001 69 MASKSEED G9 MAS Km asked message masked message masked seed 55 Optimal Assymetric Encryption Padding 2 BellareRogaway D Bending S masked message masked seed MAS Km asked message MASKSEED V 1 RSA signature Alice Bob Message Signamre Message Signamre Hash Value 1 Hash Value yes no Hash Value 2 Public k I 9y algorithm Alice 5 publi7c key Public key algorithm Alice s private key


Buy Material

Are you sure you want to buy this material for

25 Karma

Buy Material

BOOM! Enjoy Your Free Notes!

We've added these Notes to your profile, click here to view them now.


You're already Subscribed!

Looks like you've already subscribed to StudySoup, you won't need to purchase another subscription to get this material. To access this material simply click 'View Full Document'

Why people love StudySoup

Bentley McCaw University of Florida

"I was shooting for a perfect 4.0 GPA this semester. Having StudySoup as a study aid was critical to helping me achieve my goal...and I nailed it!"

Amaris Trozzo George Washington University

"I made $350 in just two days after posting my first study guide."

Jim McGreen Ohio University

"Knowing I can count on the Elite Notetaker in my class allows me to focus on what the professor is saying instead of just scribbling notes the whole time and falling behind."


"Their 'Elite Notetakers' are making over $1,200/month in sales by creating high quality content that helps their classmates in a time of need."

Become an Elite Notetaker and start selling your notes online!

Refund Policy


All subscriptions to StudySoup are paid in full at the time of subscribing. To change your credit card information or to cancel your subscription, go to "Edit Settings". All credit card information will be available there. If you should decide to cancel your subscription, it will continue to be valid until the next payment period, as all payments for the current period were made in advance. For special circumstances, please email


StudySoup has more than 1 million course-specific study resources to help students study smarter. If you’re having trouble finding what you’re looking for, our customer support team can help you find what you need! Feel free to contact them here:

Recurring Subscriptions: If you have canceled your recurring subscription on the day of renewal and have not downloaded any documents, you may request a refund by submitting an email to

Satisfaction Guarantee: If you’re not satisfied with your subscription, you can contact us for further help. Contact must be made within 3 business days of your subscription purchase and your refund request will be subject for review.

Please Note: Refunds can never be provided more than 30 days after the initial purchase date regardless of your activity on the site.