Tutorial 7: RSA

Alice on the left. Bob is on the right

Step 4.i 4.ii Step 4.i 4.ii
P Q N=PQ P Q N=PQ
1187 1777 2109299 1499 1999 2996501
P-1 Q-1 f(N) P-1 Q-1 f(N)
1186 1776 2106336 1498 1998 2993004
Step 4.iii 4.iv Step 4.iii 4.iv
EA DA EB DB
181 1349917 197 881189
Alice will encrypt to Bob
Step 5.i Bob Public Key
MA CA EB NB
19596 928549 197 2996501

i Left Right ei
7 19596 451088 1 2996501
6 2838999 2983339 1 2996501
5 1844726 2459133 0 2996501
4 1696414 2743151 0 2996501
3 1874503 1651530 0 2996501
2 1885953 1288155 1 2996501
1 1996219 1583470 0 2996501
0 928549 1092132 1 2996501

Step 5.ii Bob received the ciphertext

Bob Private Key
CA DB NB
928549 881189 2996501
2996501
Left Right di 2996501
928549 2033665 1 2996501 1101 0111 0010 0010 010
1626398 1676518 1 2996501
207151 1458208 0 2996501
969101 2521147 1 2996501
2394284 1044481 0 2996501
300036 1443790 1 2996501
2805876 1657446 1 2996501
421690 1049138 1 2996501
1097257 1602578 0 2996501
2794257 250215 0 2996501
426428 1650832 1 2996501
1172500 1997669 0 2996501
 545713 955333 0 2996501
1419486 400447 0 2996501
1660045 48794 1 2996501
2274870 1817199 0 2996501
1377375 2611558 0 2996501
2008319 1142298 1 2996501
922743 1583470 0 2996501
19596 1092132 1 2996501

Step 5.iii Bob will encrypt to Alice

Alice Public Key
EA NA MB CB
181 2109299 12345 1236110

eAi Left Right

1 2109299 12345 529497
0 2109299 529497 2032163
1 2109299 1185244 1739316
1 2109299 1021949 243086
0 2109299 435432 914188
1 2109299 1911235 1686760
0 2109299 605294 1217372
1 2109299 1236110 1108984

Step 5.iv Alice will decrypt a messag from Bob

Alice Private Key
CB DA NA
1236110 1349917 2109299

Left Right
1236110 173696 1 2109299 0001 0100 1001 1001 0001 1101
173696 1817350 0 2109299
1393054 1664609 1 2109299
71637 730751 0 2109299
2044601 226805 0 2109299
563253 1033312 1 2109299
607316 1429464 0 2109299
700716 1622699 0 2109299
1887049 200755 1 2109299
202997 194032 1 2109299
516745 973677 0 2109299
797419 1084400 0 2109299
1382756 1823294 1 2109299
305 1558328 0 2109299
93025 697765 0 2109299
 1306127 130998 0 2109299
17763 1328639 1 2109299
1777345 822025 1 2109299
1306182 619480 1 2109299
702376 1217372 0 2109299
12345 1108984 1 2109299

Step 5.v Bob will sign the message

Bob Private Key
MB SB DB NB
12345 143559 881189 2996501

Left Right di 2996501 1101 0111 0010 0010 0101

12345 2573975 1 2996501
824771 2684098 1 2996501
2520928 2193275 0 2996501
1647519 1369768 1 2996501
1351032 2961975 0 2996501
800235 2433779 1 2996501
1334109 806109 1 2996501
2052484 2499025 1 2996501
2705887 2178368 0 2996501
116311 535316 0 2996501
1841498 1836224 1 2996501
1670813 1270102 0 2996501
836844 1900233 0 2996501
1624628 451467 0 2996501
393502 454069 1 2996501
2631330 1698010 0 2996501
2568240 1942220 0 2996501
657663 1328526 1 2996501
2670728 2633158 0 2996501
1101 0111 0010 0010 0101 2553138 1291092 1 2996501

Step 5.vi Alice will verify Bob signature

Bob Public Key
SB EB NB
2553138 197 2996501
Left Right ei
2553138 284169 1 2996501
860699 2311613 1 2996501
1798379 1246012 0 2996501
1547327 387742 0 2996501
1563424 1238913 0 2996501
2078710 1721337 1 2996501
2913074 2633158 0 2996501
12345 1291092 1 2996501
1101 0111 0010 0010 0101
1101 0111 0010 0010 0101
 Extended Euclidean Algorithm
i b= a* q + r u v w
0 666400 181 3681 139 0 1 -3681
1 181 139 1 42 1 -3681 3682
2 139 42 3 13 -3681 3682 -14727
3 42 13 3 3 3682 -14727 47863
4 13 3 4 1 -14727 47863 -206179

a-1 460221 a*a-1 -37318399 º 1

Extended Euclidean Algorithm

i b= a* q + r u v w
0 718740 197 3648 84 0 1 -3648
1 197 84 2 29 1 -3648 7297
2 84 29 2 26 -3648 7297 -18242
3 29 26 1 3 7297 -18242 25539
4 26 3 8 2 -18242 25539 -222554
5 3 2 1 1 25539 -222554 248093

a-1 248093 a*a-1 48874321 º 1

Extended Euclidean Algorithm

i b= a* q + r u v w
0 697200 181 3851 169 0 1 -3851
1 181 169 1 12 1 -3851 3852
2 169 12 14 1 -3851 3852 -57779
3 12 1 12 0 3852 -57779 697200

a-1 639421 a*a-1 115735201 º 1

Extended Euclidean Algorithm

i b= a* q + r u v w
0 523848 197 2659 25 0 1 -2659
1 197 25 7 22 1 -2659 18614
2 25 22 1 3 -2659 18614 -21273
3 22 3 7 1 18614 -21273 167525
4 3 1 3 0 -21273 167525 -523848

a-1 167525 a*a-1 33002425 º 1

Extended Euclidean Algorithm

i b= a* q + r u v w
0 623616 139 4486 62 0 1 -4486
 1 139 62 2 15 1 -4486 8973
2 62 15 4 2 -4486 8973 -40378
3 15 2 7 1 8973 -40378 291619
4 2 1 2 0 -40378 291619 -623616

a-1 291619 a*a-1 40535041 º 1

Extended Euclidean Algorithm

i b= a* q + r u v w
0 523872 103 5086 14 0 1 -5086
1 103 14 7 5 1 -5086 35603
2 14 5 2 4 -5086 35603 -76292
3 5 4 1 1 35603 -76292 111895
4 4 1 4 0 -76292 111895 -523872

a-1 111895 a*a-1 11525185 º 1

Extended Euclidean Algorithm

i b= a* q + r u v w
0 598780 137 4370 90 0 1 -4370
1 137 90 1 47 1 -4370 4371
2 90 47 1 43 -4370 4371 -8741
3 47 43 1 4 4371 -8741 13112
4 43 4 10 3 -8741 13112 -139861
5 4 3 1 1 13112 -139861 152973
6 3 1 3 0 -139861 152973 -598780

a-1 152973 a*a-1 20957301 º 1

Extended Euclidean Algorithm

i b= a* q + r u v w
0 495144 79 6267 51 0 1 -6267
1 79 51 1 28 1 -6267 6268
2 51 28 1 23 -6267 6268 -12535
3 28 23 1 5 6268 -12535 18803
4 23 5 4 3 -12535 18803 -87747
5 5 3 1 2 18803 -87747 106550
6 3 2 1 1 -87747 106550 -194297
7 2 1 2 0 106550 -194297 495144

a-1 300847 a*a-1 23766913 º 1

Extended Euclidean Algorithm

i b= a* q + r u v w
0 2106336 181 11637 39 0 1 -11637
 1 181 39 4 25 1 -11637 46549
2 39 25 1 14 -11637 46549 -58186
3 25 14 1 11 46549 -58186 104735
4 14 11 1 3 -58186 104735 -162921
5 11 3 3 2 104735 -162921 593498
6 3 2 1 1 -162921 593498 -756419
7 2 1 2 0 593498 -756419 2106336
a-1 1349917 a*a-1 -136911839 º 1

Extended Euclidean Algorithm

i b= a* q + r u v w
0 437016 13 33616 8 0 1 -33616
1 13 8 1 5 1 -33616 33617
2 8 5 1 3 -33616 33617 -67233
3 5 3 1 2 33617 -67233 100850
4 3 2 1 1 -67233 100850 -168083
5 2 1 2 0 100850 -168083 437016
6 1 0 #DIV/0! #DIV/0! -168083 437016 #DIV/0!
a-1 437016 a*a-1 5681208 º 0
(mod b)

(mod b)

(mod b)

(mod b)
(mod b)

(mod b)

(mod b)

(mod b)
(mod b)

(mod b)
Tutorial 7: RSA

Alice on the left. Bob is on the right

Step 4.i 4.ii Step 4.i 4.ii
P Q
N=PQ P Q
N=PQ
701 997 698897 599 877 525323
P-1 Q-1 f(N) P-1 Q-1 f(N)
700 996 697200 598 876 523848
Step 4.iii 4.iv Step 4.iii 4.iv
EA DA EB DB
181 639421 197 167525

Step 5.i Bob Public Key

MA CA EB NB
19596 497855 197 525323
Alice will encrypt to Bob
i Left Right ei
7 19596 517426 1 525323
6 220673 374495 1 525323
5 181475 272713 0 525323
4 151432 437168 0 525323
3 251028 20116 0 525323
2 274572 154746 1 525323
1 154131 269149 0 525323
0 497855 193147 1 525323

Step 5.ii Bob received the ciphertext

Bob will decrypt using his Private Key
CA DB NB
497855 167525 525323
525323
Left Right di
497855 127196 1 525323
127196 103545 0 525323
136887 249918 1 525323
304682 440860 0 525323
243148 167358 0 525323
48838 192758 0 525323
127044 76097 1 525323
148099 117980 1 525323
477040 322192 1 525323
389938 518986 0 525323
53432 82286 0 525323
277365 97649 1 525323
336974 189428 1 525323
 283611 313142 0 525323
368176 460028 0 525323
304529 440880 1 525323
16036 269149 0 525323
19596 193147 1 525323

Step 5.iii Bob will encrypt to Alice

using her Public Key
MB EA NA
12345 181 698897
698897
Left Right ei
12345 39479 1 698897
39479 237046 0 698897
108204 186213 1 698897
489839 205611 1 698897
422366 336650 0 698897
317044 84980 1 698897
133602 618667 0 698897
94829 11530 1 698897

Step 5.iv Alice will decrypt

using her Private Key
CB DA NA
94829 639421 698897
698897
Left Right di
94829 530439 1 698897
530439 683944 0 698897
83976 127686 0 698897
81762 544277 1 698897
307393 174721 1 698897
573491 305778 1 698897
84542 684728 0 698897
429042 33860 0 698897
148110 89078 0 698897
291961 263911 0 698897
252916 421912 0 698897
2535 669844 1 698897
433727 508130 1 698897
499524 219427 0 698897
337341 495102 1 698897
691001 447800 1 698897
590020 108348 1 698897
77267 615092 1 698897
211115 618667 0 698897
12345 11530 1 698897
Step 5.v Bob will sign the message
 using his Private Key
MB DB NB
12345 167525 525323
525323
Left Right di
12345 55355 1 525323
55355 437575 0 525323
371241 52293 1 525323
340385 519471 0 525323
384606 91796 0 525323
274250 434838 0 525323
221947 376270 1 525323
349734 361816 1 525323
78027 326256 1 525323
244482 149655 0 525323
197384 257406 0 525323
161313 434815 1 525323
185135 336525 1 525323
269090 298721 0 525323
481749 9722 0 525323
309233 484467 1 525323
502599 520025 0 525323
92785 226685 1 525323

Step 5.vi Alice will verify a signature from Bob

using Bob Public Key
SB EB NB
92785 197 525323
525323
Left Right ei
92785 62901 1 525323
456078 328288 1 525323
247004 524942 0 525323
488119 449616 0 525323
436834 346625 0 525323
59699 166003 1 525323
179369 520025 0 525323
12345 226685 1 525323
Tutorial 7: RSA

Alice on the left. Bob is on the right

Step 4.i 4.ii Step 4.i 4.ii
index P Q N=PQ P Q N=PQ
10 673 929 625217 613 857 525341
P-1 Q-1 f(N) P-1 Q-1 f(N)
672 928 623616 612 856 523872
Step 4.iii 4.iv Step 4.iii 4.iv
EA DA EA DA
139 291619 103 111895

Step 5.i Bob Public Key

MA CA EB NB
19596 523408 103 525341
Alice will encrypt to Bob
i Left Right ei
6 19596 504286 1 525341
5 324246 450562 1 525341
4 24868 322221 0 525341
3 91067 490896 0 525341
2 8296 238047 1 525341
1 81093 467244 1 525341
0 523408 470825 1 525341

Step 5.ii Bob received the ciphertext

Bob will decrypt using his Private Key
CA DB NB
523408 111895 525341
525341
Left Right di
523408 59102 1 525341
1 1011 0101 0001 0111 280172 54095 1 525341
422705 341831 0 525341
206828 511318 1 525341
58617 166995 1 525341
222549 67062 0 525341
168569 392884 1 525341
338412 424490 0 525341
114794 322441 1 525341
8792 341317 0 525341
74137 111272 0 525341
177227 467882 0 525341
449092 293837 1 525341
486495 490896 0 525341
6943 238047 1 525341
 37535 467244 1 525341
19596 470825 1 525341

Step 5.iii Bob will encrypt to Alice

using her Public Key
MB EA NA
12345 139 625217
625217
Left Right ei
12345 471294 1 625217
471294 480245 0 625217
316931 530426 0 625217
396409 95646 0 625217
525900 607389 1 625217
443097 8932 0 625217
118794 378065 1 625217
15632 410204 1 625217

Step 5.iv Alice will decrypt

using her Private Key
CB DA NA
15632 291619 625217
625217
Left Right di 100 0111 0011 0010 0011
15632 524794 1 625217
524794 107551 0 625217
28719 29602 0 625217
119738 469935 0 625217
172247 380702 1 625217
142783 584383 1 625217
372720 587034 1 625217
107085 246811 0 625217
92228 582911 0 625217
181529 426582 1 625217
127126 294006 1 625217
410860 334496 0 625217
475685 202139 0 625217
492134 368720 1 625217
562930 417702 0 625217
198884 375764 0 625217
491951 8932 0 625217
81256 378065 1 625217
12345 410204 1 625217

Step 5.v Bob will sign the message

 using his Private Key
MB DB NB
12345 111895 525341
525341
Left Right di 1 1011 0101 0001 0111
12345 50135 1 525341
64877 286881 1 525341
518378 197689 0 525341
410254 298390 1 525341
205899 223397 1 525341
430183 462307 0 525341
371175 131173 1 525341
203375 59736 0 525341
298375 273624 1 525341
202719 366872 0 525341
193236 450280 0 525341
489439 177614 0 525341
416571 5946 1 525341
233580 473692 0 525341
282645 462944 1 525341
22646 83458 1 525341
338291 266786 1 525341

Step 5.vi Alice will verify a signature from Bob

using Bob Public Key
SB EB NB
338291 103 525341
525341
Left Right ei 110 0111
338291 517241 1 525341
21556 467716 1 525341
259692 266965 0 525341
334671 473692 0 525341
397785 462944 1 525341
195582 83458 1 525341
12345 266786 1 525341
Tutorial 7: RSA

Alice on the left. Bob is on the right

Step 4.i 4.ii Step 4.i 4.ii
index P QN=PQ index P Q
N=PQ
9 659 911 600349 3 599 829 496571
P-1 Q-1 f(N) P-1 Q-1 f(N)
658 910 598780 598 828 495144
Step 4.iii 4.iv Step 4.iii 4.iv
EA DA EB DB
137 152973 79 300847

Step 5.i Bob Public Key

MA CA EB NB
19596 413293 79 496571
496571
Alice will encrypt to Bob
i Left Right ei 100 1111
6 19596 153833 1 496571
5 153833 325498 0 496571
4 4313 100478 0 496571
351702 43483 1 496571
160979 325492 1 496571
197890 129501 1 496571
413293 313189 1 496571

Step 5.iiBob received the ciphertext

Bob will decrypt using his Private Key
CA DB NB
413293 300847 496571
496571
Left Right di 100 1001 0111 0010 1111
413293 114698 1 496571
114698 219712 0 496571
472272 45297 0 496571
226104 483408 1 496571
41224 239622 0 496571
152214 386996 0 496571
474269 90416 1 496571
311633 117199 0 496571
278917 451741 1 496571
305241 106063 1 496571
333267 40535 1 496571
347432 260361 0 496571
33089 383308 0 496571
358501 91955 1 496571
 460781 100478 0 496571
59562 43483 1 496571
316681 325492 1 496571
413585 129501 1 496571
19596 313189 1 496571

Step 5.iii Bob will encrypt to Alice

using her Public Key
MB EA NA
12345 137 600349
600349
Left Right ei 1000 1001
12345 510728 1 600349
510728 71962 0 600349
454719 242905 0 600349
168126 108977 0 600349
416320 482960 1 600349
385402 21865 0 600349
554467 316166 0 600349
504824 429660 1 600349

Step 5.iv Alice will decrypt

using her Private Key
CB DA NA
504824 152973 600349
600349
Left Right di 10 0101 0101 1000 1101
504824 321174 1 600349
321174 88946 0 600349
172747 135788 0 600349
133508 462456 1 600349
24254 483790 0 600349
21455 102611 1 600349
449691 39222 0 600349
127131 271146 1 600349
295732 223244 0 600349
15078 511650 1 600349
174050 539305 1 600349
392309 268402 0 600349
281492 108410 0 600349
82950 207701 0 600349
582697 427308 1 600349
544369 180957 1 600349
538969 316166 0 600349
12345 429660 1 600349
 Step 5.v Bob will sign the message
using his Private Key
MB DB NB
12345 300847 496571
496571
Left Right di 100 1001 0111 0010 1111
12345 448299 1 496571
448299 463931 0 496571
274852 474868 0 496571
194467 270901 1 496571
56442 87377 0 496571
196399 286033 0 496571
14508 335700 1 496571
432531 463803 0 496571
450245 155322 1 496571
363389 14791 1 496571
2195 282441 1 496571
348886 237387 0 496571
467763 406647 0 496571
416256 163612 1 496571
41935 260593 0 496571
426029 144544 1 496571
166066 239682 1 496571
382507 155276 1 496571
292764 127842 1 496571

Step 5.vi Alice will verify a signature from Bob

using Bob Public Key
SB EB NB
292764 79 496571
496571
Left Right ei 100 1111
292764 122241 1 496571
122241 388725 0 496571
47549 260593 0 496571
394 144544 1 496571
341242 239682 1 496571
348776 155276 1 496571
12345 127842 1 496571
1 0111 0010 1111