{"id":101,"date":"2018-07-11T11:06:17","date_gmt":"2018-07-11T11:06:17","guid":{"rendered":"http:\/\/itp4.epgpbooks.inflibnet.ac.in\/?post_type=chapter&#038;p=101"},"modified":"2019-05-13T12:08:34","modified_gmt":"2019-05-13T12:08:34","slug":"public-key-algorithm-part-1","status":"publish","type":"chapter","link":"https:\/\/ebooks.inflibnet.ac.in\/itp4\/chapter\/public-key-algorithm-part-1\/","title":{"rendered":"Public key Algorithm Part 1"},"content":{"raw":"<div><span style=\"float: right;\"><a href=\"https:\/\/youtu.be\/yNJUBuJ_QS8\" target=\"_blank\" rel=\"noopener\"><img src=\"http:\/\/epgpbooks.inflibnet.ac.in\/wp-content\/uploads\/2018\/11\/download.png\" alt=\"epgp books\" width=\"75px\" height=\"75px;\" \/><\/a>\r\n<\/span><\/div>\r\n\r\n<strong>The modulus:<\/strong>\r\n<ul>\r\n \t<li>\u00a8 Let a be an integer and n a positive integer. a mod n gives the remainder when a is divided by n.<\/li>\r\n \t<li>\u00a8 n is called modulus.<\/li>\r\n \t<li>\u00a8 a = qn + r 0&lt;=r&lt;n; q=\u2514a\/n\u2518<\/li>\r\n \t<li>\u00a8 a= \u2514a\/n\u2518xn + (a mod n)<\/li>\r\n<\/ul>\r\n<strong>Congruent modulo n:<\/strong>\r\n<ul>\r\n \t<li>\u00a8 if (a mod n) = ( b mod n) then a \u2261 b (mod n)<\/li>\r\n \t<li>\u00a8 73 \u2261 4 ( mod 23) as<\/li>\r\n<\/ul>\r\n73 mod 23 = 4 and\r\n\r\n4 mod 23 = 4.\r\n<ul>\r\n \t<li>Is 21 \u2261 -9 (mod 10) ?<\/li>\r\n \t<li>\u00a8 21 mod 10 =1<\/li>\r\n \t<li>\u00a8 -9 mod 10<\/li>\r\n<\/ul>\r\n-9 = 10x-1 + 1\r\n\r\nso -9 mod 10 = 1.\r\n<ul>\r\n \t<li>\u00a8 So It is true that 21 \u2261 -9 (mod 10)<\/li>\r\n<\/ul>\r\n<img class=\"size-full wp-image-102 aligncenter\" src=\"http:\/\/itp4.epgpbooks.inflibnet.ac.in\/wp-content\/uploads\/sites\/25\/2018\/07\/Untitled-60.png\" alt=\"\" width=\"613\" height=\"248\" \/>\r\n\r\n<img class=\"size-full wp-image-103 aligncenter\" src=\"http:\/\/itp4.epgpbooks.inflibnet.ac.in\/wp-content\/uploads\/sites\/25\/2018\/07\/Untitled-61.png\" alt=\"\" width=\"528\" height=\"803\" \/>\r\n\r\n<img class=\"size-full wp-image-104 aligncenter\" src=\"http:\/\/itp4.epgpbooks.inflibnet.ac.in\/wp-content\/uploads\/sites\/25\/2018\/07\/Untitled-62.png\" alt=\"\" width=\"750\" height=\"400\" \/>\r\n\r\n<img class=\"size-full wp-image-105 aligncenter\" src=\"http:\/\/itp4.epgpbooks.inflibnet.ac.in\/wp-content\/uploads\/sites\/25\/2018\/07\/Untitled-63.png\" alt=\"\" width=\"810\" height=\"561\" \/>\r\n\r\n<strong>Practical public key cryptosystem \u2013 suitable trap door one way function:<\/strong>\r\n\r\n&nbsp;\r\n<ul>\r\n \t<li>\u00a8 Y=fk(X) easy if k and X are known<\/li>\r\n \t<li>\u00a8 X=fk-1(Y) easy, if k and Y are known<\/li>\r\n \t<li>\u00a8 X=fk-1(Y) infeaible, if Y is known but k is not known<\/li>\r\n<\/ul>\r\n&nbsp;\r\n\r\n<strong>RSA algorithm:<\/strong>\r\n\r\n&nbsp;\r\n<ol>\r\n \t<li>p,q two prim numbers<\/li>\r\n \t<li>n=pq<\/li>\r\n \t<li>Encryption key e, with GCD(\u0424(n),e) =1; 1&lt;e&lt; \u0424(n), \u0424(n) is called totient function.<\/li>\r\n \t<li>d=e-1 (mod \u0424(n))<\/li>\r\n \t<li>C=Me mod n, M is the message to be transmitted. C is the ciphertext.<\/li>\r\n \t<li>M= Cd mod n<\/li>\r\n<\/ol>\r\nPrivate key consist of [d,n] and public key consist of [e,n]\r\n\r\n&nbsp;\r\n\r\n<strong>Greatest common divisor and relatively primenumbers :<\/strong>\r\n\r\n&nbsp;\r\n<ul>\r\n \t<li>\u00a8 GCD (a,b) of a and b is the largest number that divides a,b. GCD(16,12) = 4<\/li>\r\n \t<li>\u00a8 When no common factors (except 1) , then numbers are relatively prime GCD(8,15) = 1<\/li>\r\n<\/ul>\r\n&nbsp;\r\n\r\nhence 8 &amp; 15 are relatively prime\r\n\r\n&nbsp;\r\n\r\n<strong>\u0424(n) totient function:<\/strong>\r\n\r\n&nbsp;\r\n<ul>\r\n \t<li>\u00a8 \u0424(n) is number of positive integers less than n and relatively prime to n.<\/li>\r\n \t<li>\u00a8 \u0424(1) = 1<\/li>\r\n \t<li>\u00a8 To calculate \u0424(24) , take all the positive integers less than 24 that are relatively prime to 24<\/li>\r\n<\/ul>\r\n&nbsp;\r\n\r\n1,5,7,11,13,17,19,23\r\n\r\n&nbsp;\r\n\r\nThere are 8 numbers so \u0424(24) = 8.\r\n\r\n&nbsp;\r\n\r\n<strong>Euclidean algorithm to find GCD(greatest common divisor) - uses theorem that: GCD(a,b) = GCD(b, a mod b)<\/strong>\r\n\r\n&nbsp;\r\n\r\nEUCLID(a,b)\r\n<ol>\r\n \t<li>A = a; B = b<\/li>\r\n \t<li>if B = 0 return A = gcd(a, b)<\/li>\r\n \t<li>R = A mod B<\/li>\r\n \t<li>A = B<\/li>\r\n \t<li>B = R<\/li>\r\n \t<li>goto 2<\/li>\r\n<\/ol>\r\n<strong>Example GCD(576,132):<\/strong>\r\n\r\n&nbsp;\r\n<table class=\"aligncenter\" border=\"1\">\r\n<tbody>\r\n<tr>\r\n<td style=\"width: 246.063px\">576<\/td>\r\n<td style=\"width: 200.063px\">= 132 x 2 + 48<\/td>\r\n<td style=\"width: 200.063px\">GCD(576,132)<\/td>\r\n<\/tr>\r\n<tr>\r\n<td style=\"width: 246.063px\">132<\/td>\r\n<td style=\"width: 200.063px\">= 48 x 2 + 36<\/td>\r\n<td style=\"width: 200.063px\">GCD(132,48)<\/td>\r\n<\/tr>\r\n<tr>\r\n<td style=\"width: 246.063px\">48 = 36x1 + 12<\/td>\r\n<td style=\"width: 200.063px\">GCD(48,36)<\/td>\r\n<\/tr>\r\n<tr>\r\n<td style=\"width: 246.063px\">36= 12x3 + 0<\/td>\r\n<td style=\"width: 200.063px\">GCD(36,12)<\/td>\r\n<\/tr>\r\n<tr>\r\n<td style=\"width: 246.063px\">GCD(576,132)=12<\/td>\r\n<td style=\"width: 200.063px\"><\/td>\r\n<\/tr>\r\n<\/tbody>\r\n<\/table>\r\n&nbsp;\r\n\r\n<strong>To find multiplicative inverse b<\/strong><strong>-1<\/strong><strong> mod m EXTENDED EUCLID(m, b):<\/strong>\r\n\r\n&nbsp;\r\n\r\nEXTENDED EUCLID(<em>m<\/em>, <em>b<\/em>)\r\n\r\n&nbsp;\r\n<ol>\r\n \t<li>(A1, A2, A3)=(1, 0, <em>m<\/em>); (B1, B2, B3)=(0, 1, <em>b<\/em>)<\/li>\r\n \t<li>if B3 = 0<\/li>\r\n<\/ol>\r\nreturn A3 = gcd(<em>m<\/em>, <em>b<\/em>); no inverse\r\n<ol start=\"3\">\r\n \t<li>if B3 = 1<\/li>\r\n<\/ol>\r\nreturn B3 = gcd(<em>m<\/em>, <em>b<\/em>); B2 = <em>b<\/em>\u20131 mod <em>m<\/em>\r\n<ol start=\"4\">\r\n \t<li>Q = A3 div B3<\/li>\r\n \t<li>(T1, T2, T3)=(A1 \u2013 Q B1, A2 \u2013 Q B2, A3 \u2013 Q B3)<\/li>\r\n \t<li>(A1, A2, A3)=(B1, B2, B3)<\/li>\r\n \t<li>(B1, B2, B3)=(T1, T2, T3)<\/li>\r\n \t<li>goto 2<\/li>\r\n<\/ol>\r\n&nbsp;\r\n\r\n<strong>Inverse of 550 mod 1759:<\/strong>\r\n<table class=\"aligncenter\" border=\"1\">\r\n<tbody>\r\n<tr>\r\n<td style=\"width: 64.0625px\">Q<\/td>\r\n<td style=\"width: 74.0625px\">A1<\/td>\r\n<td style=\"width: 80.0625px\">A2<\/td>\r\n<td style=\"width: 113.063px\">A3<\/td>\r\n<td style=\"width: 74.0625px\">B1<\/td>\r\n<td style=\"width: 80.0625px\">B2<\/td>\r\n<td style=\"width: 105.063px\">B3<\/td>\r\n<\/tr>\r\n<tr>\r\n<td style=\"width: 64.0625px\"><\/td>\r\n<td style=\"width: 74.0625px\"><\/td>\r\n<td style=\"width: 80.0625px\"><\/td>\r\n<td style=\"width: 113.063px\"><\/td>\r\n<td style=\"width: 74.0625px\"><\/td>\r\n<td style=\"width: 80.0625px\"><\/td>\r\n<td style=\"width: 105.063px\"><\/td>\r\n<\/tr>\r\n<tr>\r\n<td style=\"width: 64.0625px\">-<\/td>\r\n<td style=\"width: 74.0625px\">1<\/td>\r\n<td style=\"width: 80.0625px\">0<\/td>\r\n<td style=\"width: 113.063px\">1759<\/td>\r\n<td style=\"width: 74.0625px\">0<\/td>\r\n<td style=\"width: 80.0625px\">1<\/td>\r\n<td style=\"width: 105.063px\">550<\/td>\r\n<\/tr>\r\n<tr>\r\n<td style=\"width: 64.0625px\"><\/td>\r\n<td style=\"width: 74.0625px\"><\/td>\r\n<td style=\"width: 80.0625px\"><\/td>\r\n<td style=\"width: 113.063px\"><\/td>\r\n<td style=\"width: 74.0625px\"><\/td>\r\n<td style=\"width: 80.0625px\"><\/td>\r\n<td style=\"width: 105.063px\"><\/td>\r\n<\/tr>\r\n<\/tbody>\r\n<\/table>\r\n&nbsp;\r\n<table class=\"aligncenter\" border=\"1\">\r\n<tbody>\r\n<tr>\r\n<td style=\"width: 57.0625px\">3<\/td>\r\n<td style=\"width: 101.063px\">0<\/td>\r\n<td style=\"width: 101.063px\">1<\/td>\r\n<td style=\"width: 85.0625px\">550<\/td>\r\n<td style=\"width: 81.0625px\">1<\/td>\r\n<td style=\"width: 83.0625px\">-3<\/td>\r\n<td style=\"width: 82.0625px\">109<\/td>\r\n<\/tr>\r\n<tr>\r\n<td style=\"width: 57.0625px\"><\/td>\r\n<td style=\"width: 101.063px\"><\/td>\r\n<td style=\"width: 101.063px\"><\/td>\r\n<td style=\"width: 85.0625px\"><\/td>\r\n<td style=\"width: 81.0625px\"><\/td>\r\n<td style=\"width: 83.0625px\"><\/td>\r\n<td style=\"width: 82.0625px\"><\/td>\r\n<\/tr>\r\n<tr>\r\n<td style=\"width: 57.0625px\">5<\/td>\r\n<td style=\"width: 101.063px\">1<\/td>\r\n<td style=\"width: 101.063px\">-3<\/td>\r\n<td style=\"width: 85.0625px\">109<\/td>\r\n<td style=\"width: 81.0625px\">-5<\/td>\r\n<td style=\"width: 83.0625px\">16<\/td>\r\n<td style=\"width: 82.0625px\">5<\/td>\r\n<\/tr>\r\n<tr>\r\n<td style=\"width: 57.0625px\"><\/td>\r\n<td style=\"width: 101.063px\"><\/td>\r\n<td style=\"width: 101.063px\"><\/td>\r\n<td style=\"width: 85.0625px\"><\/td>\r\n<td style=\"width: 81.0625px\"><\/td>\r\n<td style=\"width: 83.0625px\"><\/td>\r\n<td style=\"width: 82.0625px\"><\/td>\r\n<\/tr>\r\n<tr>\r\n<td style=\"width: 57.0625px\">21<\/td>\r\n<td style=\"width: 101.063px\">-5<\/td>\r\n<td style=\"width: 101.063px\"><\/td>\r\n<td style=\"width: 85.0625px\">5<\/td>\r\n<td style=\"width: 81.0625px\">106<\/td>\r\n<td style=\"width: 83.0625px\"><\/td>\r\n<td style=\"width: 82.0625px\"><\/td>\r\n<\/tr>\r\n<tr>\r\n<td style=\"width: 57.0625px\">16<\/td>\r\n<td style=\"width: 101.063px\">-339<\/td>\r\n<td style=\"width: 101.063px\">4<\/td>\r\n<\/tr>\r\n<tr>\r\n<td style=\"width: 57.0625px\"><\/td>\r\n<td style=\"width: 101.063px\"><\/td>\r\n<td style=\"width: 101.063px\"><\/td>\r\n<td style=\"width: 85.0625px\"><\/td>\r\n<td style=\"width: 81.0625px\"><\/td>\r\n<td style=\"width: 83.0625px\"><\/td>\r\n<td style=\"width: 82.0625px\"><\/td>\r\n<\/tr>\r\n<tr>\r\n<td style=\"width: 57.0625px\">1<\/td>\r\n<td style=\"width: 101.063px\">106<\/td>\r\n<td style=\"width: 101.063px\">-339<\/td>\r\n<td style=\"width: 85.0625px\">4<\/td>\r\n<td style=\"width: 81.0625px\">-111<\/td>\r\n<td style=\"width: 83.0625px\">355<\/td>\r\n<td style=\"width: 82.0625px\">1<\/td>\r\n<\/tr>\r\n<tr>\r\n<td style=\"width: 57.0625px\"><\/td>\r\n<td style=\"width: 101.063px\"><\/td>\r\n<td style=\"width: 101.063px\"><\/td>\r\n<td style=\"width: 85.0625px\"><\/td>\r\n<td style=\"width: 81.0625px\"><\/td>\r\n<td style=\"width: 83.0625px\"><\/td>\r\n<td style=\"width: 82.0625px\"><\/td>\r\n<\/tr>\r\n<\/tbody>\r\n<\/table>\r\n&nbsp;\r\n<table>\r\n<tbody>\r\n<tr>\r\n<td><strong>you can view video on Public key Algorithm Part 1<\/strong><\/td>\r\n<td><a href=\"https:\/\/youtu.be\/yNJUBuJ_QS8\" target=\"_blank\" rel=\"noopener\"><img class=\"alignnone wp-image-120\" src=\"http:\/\/epgpbooks.inflibnet.ac.in\/wp-content\/uploads\/2018\/11\/download.png\" alt=\"\" width=\"36\" height=\"36\" \/><\/a><\/td>\r\n<\/tr>\r\n<\/tbody>\r\n<\/table>\r\n\r\n<strong>Suggested Reading:<\/strong>\r\n\r\n&nbsp;\r\n<ol>\r\n \t<li>Cryptography and Network Security Principles and Practice by William Stallings, sixth Edition, PEARSON.<\/li>\r\n \t<li>Security in Computing by Charles Pfleeger &amp; Shari Lawrence Pfleeger, fourth Edition, PEARSON.<\/li>\r\n \t<li>Network Security by Charlie Kaufman, Radia Perlman, Mike Speciner, second Edition, PHI.<\/li>\r\n \t<li>The Complete Reference \u2013 Network Security by Roberta Bragg, Mark Rhodes-Ousley &amp; Keith Strassberg, Tata McGraw Hill<\/li>\r\n \t<li>Network Security Bible by Eric Cole, Ronald Krutz, James Conley, Wiley<\/li>\r\n \t<li>Hacking 6 Exposed by Stuart McClure, Joel Scambray &amp; George Kurtz , Tata McGraw Hill .<\/li>\r\n \t<li><a href=\"http:\/\/www.snort.org\/\">www.snort.org<\/a><\/li>\r\n \t<li><a href=\"https:\/\/nmap.org\/\">https:\/\/nmap.org<\/a><\/li>\r\n<\/ol>","rendered":"<div><span style=\"float: right;\"><a href=\"https:\/\/youtu.be\/yNJUBuJ_QS8\" target=\"_blank\" rel=\"noopener\"><img decoding=\"async\" src=\"http:\/\/epgpbooks.inflibnet.ac.in\/wp-content\/uploads\/2018\/11\/download.png\" alt=\"epgp books\" width=\"75px\" height=\"75px;\" \/><\/a><br \/>\n<\/span><\/div>\n<p><strong>The modulus:<\/strong><\/p>\n<ul>\n<li>\u00a8 Let a be an integer and n a positive integer. a mod n gives the remainder when a is divided by n.<\/li>\n<li>\u00a8 n is called modulus.<\/li>\n<li>\u00a8 a = qn + r 0&lt;=r&lt;n; q=\u2514a\/n\u2518<\/li>\n<li>\u00a8 a= \u2514a\/n\u2518xn + (a mod n)<\/li>\n<\/ul>\n<p><strong>Congruent modulo n:<\/strong><\/p>\n<ul>\n<li>\u00a8 if (a mod n) = ( b mod n) then a \u2261 b (mod n)<\/li>\n<li>\u00a8 73 \u2261 4 ( mod 23) as<\/li>\n<\/ul>\n<p>73 mod 23 = 4 and<\/p>\n<p>4 mod 23 = 4.<\/p>\n<ul>\n<li>Is 21 \u2261 -9 (mod 10) ?<\/li>\n<li>\u00a8 21 mod 10 =1<\/li>\n<li>\u00a8 -9 mod 10<\/li>\n<\/ul>\n<p>-9 = 10x-1 + 1<\/p>\n<p>so -9 mod 10 = 1.<\/p>\n<ul>\n<li>\u00a8 So It is true that 21 \u2261 -9 (mod 10)<\/li>\n<\/ul>\n<p><img loading=\"lazy\" decoding=\"async\" class=\"size-full wp-image-102 aligncenter\" src=\"http:\/\/itp4.epgpbooks.inflibnet.ac.in\/wp-content\/uploads\/sites\/25\/2018\/07\/Untitled-60.png\" alt=\"\" width=\"613\" height=\"248\" srcset=\"https:\/\/ebooks.inflibnet.ac.in\/itp4\/wp-content\/uploads\/sites\/25\/2018\/07\/Untitled-60.png 613w, https:\/\/ebooks.inflibnet.ac.in\/itp4\/wp-content\/uploads\/sites\/25\/2018\/07\/Untitled-60-300x121.png 300w, https:\/\/ebooks.inflibnet.ac.in\/itp4\/wp-content\/uploads\/sites\/25\/2018\/07\/Untitled-60-65x26.png 65w, https:\/\/ebooks.inflibnet.ac.in\/itp4\/wp-content\/uploads\/sites\/25\/2018\/07\/Untitled-60-225x91.png 225w, https:\/\/ebooks.inflibnet.ac.in\/itp4\/wp-content\/uploads\/sites\/25\/2018\/07\/Untitled-60-350x142.png 350w\" sizes=\"auto, (max-width: 613px) 100vw, 613px\" \/><\/p>\n<p><img loading=\"lazy\" decoding=\"async\" class=\"size-full wp-image-103 aligncenter\" src=\"http:\/\/itp4.epgpbooks.inflibnet.ac.in\/wp-content\/uploads\/sites\/25\/2018\/07\/Untitled-61.png\" alt=\"\" width=\"528\" height=\"803\" srcset=\"https:\/\/ebooks.inflibnet.ac.in\/itp4\/wp-content\/uploads\/sites\/25\/2018\/07\/Untitled-61.png 528w, https:\/\/ebooks.inflibnet.ac.in\/itp4\/wp-content\/uploads\/sites\/25\/2018\/07\/Untitled-61-197x300.png 197w, https:\/\/ebooks.inflibnet.ac.in\/itp4\/wp-content\/uploads\/sites\/25\/2018\/07\/Untitled-61-65x99.png 65w, https:\/\/ebooks.inflibnet.ac.in\/itp4\/wp-content\/uploads\/sites\/25\/2018\/07\/Untitled-61-225x342.png 225w, https:\/\/ebooks.inflibnet.ac.in\/itp4\/wp-content\/uploads\/sites\/25\/2018\/07\/Untitled-61-350x532.png 350w\" sizes=\"auto, (max-width: 528px) 100vw, 528px\" \/><\/p>\n<p><img loading=\"lazy\" decoding=\"async\" class=\"size-full wp-image-104 aligncenter\" src=\"http:\/\/itp4.epgpbooks.inflibnet.ac.in\/wp-content\/uploads\/sites\/25\/2018\/07\/Untitled-62.png\" alt=\"\" width=\"750\" height=\"400\" srcset=\"https:\/\/ebooks.inflibnet.ac.in\/itp4\/wp-content\/uploads\/sites\/25\/2018\/07\/Untitled-62.png 750w, https:\/\/ebooks.inflibnet.ac.in\/itp4\/wp-content\/uploads\/sites\/25\/2018\/07\/Untitled-62-300x160.png 300w, https:\/\/ebooks.inflibnet.ac.in\/itp4\/wp-content\/uploads\/sites\/25\/2018\/07\/Untitled-62-65x35.png 65w, https:\/\/ebooks.inflibnet.ac.in\/itp4\/wp-content\/uploads\/sites\/25\/2018\/07\/Untitled-62-225x120.png 225w, https:\/\/ebooks.inflibnet.ac.in\/itp4\/wp-content\/uploads\/sites\/25\/2018\/07\/Untitled-62-350x187.png 350w\" sizes=\"auto, (max-width: 750px) 100vw, 750px\" \/><\/p>\n<p><img loading=\"lazy\" decoding=\"async\" class=\"size-full wp-image-105 aligncenter\" src=\"http:\/\/itp4.epgpbooks.inflibnet.ac.in\/wp-content\/uploads\/sites\/25\/2018\/07\/Untitled-63.png\" alt=\"\" width=\"810\" height=\"561\" srcset=\"https:\/\/ebooks.inflibnet.ac.in\/itp4\/wp-content\/uploads\/sites\/25\/2018\/07\/Untitled-63.png 810w, https:\/\/ebooks.inflibnet.ac.in\/itp4\/wp-content\/uploads\/sites\/25\/2018\/07\/Untitled-63-300x208.png 300w, https:\/\/ebooks.inflibnet.ac.in\/itp4\/wp-content\/uploads\/sites\/25\/2018\/07\/Untitled-63-768x532.png 768w, https:\/\/ebooks.inflibnet.ac.in\/itp4\/wp-content\/uploads\/sites\/25\/2018\/07\/Untitled-63-65x45.png 65w, https:\/\/ebooks.inflibnet.ac.in\/itp4\/wp-content\/uploads\/sites\/25\/2018\/07\/Untitled-63-225x156.png 225w, https:\/\/ebooks.inflibnet.ac.in\/itp4\/wp-content\/uploads\/sites\/25\/2018\/07\/Untitled-63-350x242.png 350w\" sizes=\"auto, (max-width: 810px) 100vw, 810px\" \/><\/p>\n<p><strong>Practical public key cryptosystem \u2013 suitable trap door one way function:<\/strong><\/p>\n<p>&nbsp;<\/p>\n<ul>\n<li>\u00a8 Y=fk(X) easy if k and X are known<\/li>\n<li>\u00a8 X=fk-1(Y) easy, if k and Y are known<\/li>\n<li>\u00a8 X=fk-1(Y) infeaible, if Y is known but k is not known<\/li>\n<\/ul>\n<p>&nbsp;<\/p>\n<p><strong>RSA algorithm:<\/strong><\/p>\n<p>&nbsp;<\/p>\n<ol>\n<li>p,q two prim numbers<\/li>\n<li>n=pq<\/li>\n<li>Encryption key e, with GCD(\u0424(n),e) =1; 1&lt;e&lt; \u0424(n), \u0424(n) is called totient function.<\/li>\n<li>d=e-1 (mod \u0424(n))<\/li>\n<li>C=Me mod n, M is the message to be transmitted. C is the ciphertext.<\/li>\n<li>M= Cd mod n<\/li>\n<\/ol>\n<p>Private key consist of [d,n] and public key consist of [e,n]<\/p>\n<p>&nbsp;<\/p>\n<p><strong>Greatest common divisor and relatively primenumbers :<\/strong><\/p>\n<p>&nbsp;<\/p>\n<ul>\n<li>\u00a8 GCD (a,b) of a and b is the largest number that divides a,b. GCD(16,12) = 4<\/li>\n<li>\u00a8 When no common factors (except 1) , then numbers are relatively prime GCD(8,15) = 1<\/li>\n<\/ul>\n<p>&nbsp;<\/p>\n<p>hence 8 &amp; 15 are relatively prime<\/p>\n<p>&nbsp;<\/p>\n<p><strong>\u0424(n) totient function:<\/strong><\/p>\n<p>&nbsp;<\/p>\n<ul>\n<li>\u00a8 \u0424(n) is number of positive integers less than n and relatively prime to n.<\/li>\n<li>\u00a8 \u0424(1) = 1<\/li>\n<li>\u00a8 To calculate \u0424(24) , take all the positive integers less than 24 that are relatively prime to 24<\/li>\n<\/ul>\n<p>&nbsp;<\/p>\n<p>1,5,7,11,13,17,19,23<\/p>\n<p>&nbsp;<\/p>\n<p>There are 8 numbers so \u0424(24) = 8.<\/p>\n<p>&nbsp;<\/p>\n<p><strong>Euclidean algorithm to find GCD(greatest common divisor) &#8211; uses theorem that: GCD(a,b) = GCD(b, a mod b)<\/strong><\/p>\n<p>&nbsp;<\/p>\n<p>EUCLID(a,b)<\/p>\n<ol>\n<li>A = a; B = b<\/li>\n<li>if B = 0 return A = gcd(a, b)<\/li>\n<li>R = A mod B<\/li>\n<li>A = B<\/li>\n<li>B = R<\/li>\n<li>goto 2<\/li>\n<\/ol>\n<p><strong>Example GCD(576,132):<\/strong><\/p>\n<p>&nbsp;<\/p>\n<table class=\"aligncenter\">\n<tbody>\n<tr>\n<td style=\"width: 246.063px\">576<\/td>\n<td style=\"width: 200.063px\">= 132 x 2 + 48<\/td>\n<td style=\"width: 200.063px\">GCD(576,132)<\/td>\n<\/tr>\n<tr>\n<td style=\"width: 246.063px\">132<\/td>\n<td style=\"width: 200.063px\">= 48 x 2 + 36<\/td>\n<td style=\"width: 200.063px\">GCD(132,48)<\/td>\n<\/tr>\n<tr>\n<td style=\"width: 246.063px\">48 = 36&#215;1 + 12<\/td>\n<td style=\"width: 200.063px\">GCD(48,36)<\/td>\n<\/tr>\n<tr>\n<td style=\"width: 246.063px\">36= 12&#215;3 + 0<\/td>\n<td style=\"width: 200.063px\">GCD(36,12)<\/td>\n<\/tr>\n<tr>\n<td style=\"width: 246.063px\">GCD(576,132)=12<\/td>\n<td style=\"width: 200.063px\"><\/td>\n<\/tr>\n<\/tbody>\n<\/table>\n<p>&nbsp;<\/p>\n<p><strong>To find multiplicative inverse b<\/strong><strong>-1<\/strong><strong> mod m EXTENDED EUCLID(m, b):<\/strong><\/p>\n<p>&nbsp;<\/p>\n<p>EXTENDED EUCLID(<em>m<\/em>, <em>b<\/em>)<\/p>\n<p>&nbsp;<\/p>\n<ol>\n<li>(A1, A2, A3)=(1, 0, <em>m<\/em>); (B1, B2, B3)=(0, 1, <em>b<\/em>)<\/li>\n<li>if B3 = 0<\/li>\n<\/ol>\n<p>return A3 = gcd(<em>m<\/em>, <em>b<\/em>); no inverse<\/p>\n<ol start=\"3\">\n<li>if B3 = 1<\/li>\n<\/ol>\n<p>return B3 = gcd(<em>m<\/em>, <em>b<\/em>); B2 = <em>b<\/em>\u20131 mod <em>m<\/em><\/p>\n<ol start=\"4\">\n<li>Q = A3 div B3<\/li>\n<li>(T1, T2, T3)=(A1 \u2013 Q B1, A2 \u2013 Q B2, A3 \u2013 Q B3)<\/li>\n<li>(A1, A2, A3)=(B1, B2, B3)<\/li>\n<li>(B1, B2, B3)=(T1, T2, T3)<\/li>\n<li>goto 2<\/li>\n<\/ol>\n<p>&nbsp;<\/p>\n<p><strong>Inverse of 550 mod 1759:<\/strong><\/p>\n<table class=\"aligncenter\">\n<tbody>\n<tr>\n<td style=\"width: 64.0625px\">Q<\/td>\n<td style=\"width: 74.0625px\">A1<\/td>\n<td style=\"width: 80.0625px\">A2<\/td>\n<td style=\"width: 113.063px\">A3<\/td>\n<td style=\"width: 74.0625px\">B1<\/td>\n<td style=\"width: 80.0625px\">B2<\/td>\n<td style=\"width: 105.063px\">B3<\/td>\n<\/tr>\n<tr>\n<td style=\"width: 64.0625px\"><\/td>\n<td style=\"width: 74.0625px\"><\/td>\n<td style=\"width: 80.0625px\"><\/td>\n<td style=\"width: 113.063px\"><\/td>\n<td style=\"width: 74.0625px\"><\/td>\n<td style=\"width: 80.0625px\"><\/td>\n<td style=\"width: 105.063px\"><\/td>\n<\/tr>\n<tr>\n<td style=\"width: 64.0625px\">&#8211;<\/td>\n<td style=\"width: 74.0625px\">1<\/td>\n<td style=\"width: 80.0625px\">0<\/td>\n<td style=\"width: 113.063px\">1759<\/td>\n<td style=\"width: 74.0625px\">0<\/td>\n<td style=\"width: 80.0625px\">1<\/td>\n<td style=\"width: 105.063px\">550<\/td>\n<\/tr>\n<tr>\n<td style=\"width: 64.0625px\"><\/td>\n<td style=\"width: 74.0625px\"><\/td>\n<td style=\"width: 80.0625px\"><\/td>\n<td style=\"width: 113.063px\"><\/td>\n<td style=\"width: 74.0625px\"><\/td>\n<td style=\"width: 80.0625px\"><\/td>\n<td style=\"width: 105.063px\"><\/td>\n<\/tr>\n<\/tbody>\n<\/table>\n<p>&nbsp;<\/p>\n<table class=\"aligncenter\">\n<tbody>\n<tr>\n<td style=\"width: 57.0625px\">3<\/td>\n<td style=\"width: 101.063px\">0<\/td>\n<td style=\"width: 101.063px\">1<\/td>\n<td style=\"width: 85.0625px\">550<\/td>\n<td style=\"width: 81.0625px\">1<\/td>\n<td style=\"width: 83.0625px\">-3<\/td>\n<td style=\"width: 82.0625px\">109<\/td>\n<\/tr>\n<tr>\n<td style=\"width: 57.0625px\"><\/td>\n<td style=\"width: 101.063px\"><\/td>\n<td style=\"width: 101.063px\"><\/td>\n<td style=\"width: 85.0625px\"><\/td>\n<td style=\"width: 81.0625px\"><\/td>\n<td style=\"width: 83.0625px\"><\/td>\n<td style=\"width: 82.0625px\"><\/td>\n<\/tr>\n<tr>\n<td style=\"width: 57.0625px\">5<\/td>\n<td style=\"width: 101.063px\">1<\/td>\n<td style=\"width: 101.063px\">-3<\/td>\n<td style=\"width: 85.0625px\">109<\/td>\n<td style=\"width: 81.0625px\">-5<\/td>\n<td style=\"width: 83.0625px\">16<\/td>\n<td style=\"width: 82.0625px\">5<\/td>\n<\/tr>\n<tr>\n<td style=\"width: 57.0625px\"><\/td>\n<td style=\"width: 101.063px\"><\/td>\n<td style=\"width: 101.063px\"><\/td>\n<td style=\"width: 85.0625px\"><\/td>\n<td style=\"width: 81.0625px\"><\/td>\n<td style=\"width: 83.0625px\"><\/td>\n<td style=\"width: 82.0625px\"><\/td>\n<\/tr>\n<tr>\n<td style=\"width: 57.0625px\">21<\/td>\n<td style=\"width: 101.063px\">-5<\/td>\n<td style=\"width: 101.063px\"><\/td>\n<td style=\"width: 85.0625px\">5<\/td>\n<td style=\"width: 81.0625px\">106<\/td>\n<td style=\"width: 83.0625px\"><\/td>\n<td style=\"width: 82.0625px\"><\/td>\n<\/tr>\n<tr>\n<td style=\"width: 57.0625px\">16<\/td>\n<td style=\"width: 101.063px\">-339<\/td>\n<td style=\"width: 101.063px\">4<\/td>\n<\/tr>\n<tr>\n<td style=\"width: 57.0625px\"><\/td>\n<td style=\"width: 101.063px\"><\/td>\n<td style=\"width: 101.063px\"><\/td>\n<td style=\"width: 85.0625px\"><\/td>\n<td style=\"width: 81.0625px\"><\/td>\n<td style=\"width: 83.0625px\"><\/td>\n<td style=\"width: 82.0625px\"><\/td>\n<\/tr>\n<tr>\n<td style=\"width: 57.0625px\">1<\/td>\n<td style=\"width: 101.063px\">106<\/td>\n<td style=\"width: 101.063px\">-339<\/td>\n<td style=\"width: 85.0625px\">4<\/td>\n<td style=\"width: 81.0625px\">-111<\/td>\n<td style=\"width: 83.0625px\">355<\/td>\n<td style=\"width: 82.0625px\">1<\/td>\n<\/tr>\n<tr>\n<td style=\"width: 57.0625px\"><\/td>\n<td style=\"width: 101.063px\"><\/td>\n<td style=\"width: 101.063px\"><\/td>\n<td style=\"width: 85.0625px\"><\/td>\n<td style=\"width: 81.0625px\"><\/td>\n<td style=\"width: 83.0625px\"><\/td>\n<td style=\"width: 82.0625px\"><\/td>\n<\/tr>\n<\/tbody>\n<\/table>\n<p>&nbsp;<\/p>\n<table>\n<tbody>\n<tr>\n<td><strong>you can view video on Public key Algorithm Part 1<\/strong><\/td>\n<td><a href=\"https:\/\/youtu.be\/yNJUBuJ_QS8\" target=\"_blank\" rel=\"noopener\"><img loading=\"lazy\" decoding=\"async\" class=\"alignnone wp-image-120\" src=\"http:\/\/epgpbooks.inflibnet.ac.in\/wp-content\/uploads\/2018\/11\/download.png\" alt=\"\" width=\"36\" height=\"36\" \/><\/a><\/td>\n<\/tr>\n<\/tbody>\n<\/table>\n<p><strong>Suggested Reading:<\/strong><\/p>\n<p>&nbsp;<\/p>\n<ol>\n<li>Cryptography and Network Security Principles and Practice by William Stallings, sixth Edition, PEARSON.<\/li>\n<li>Security in Computing by Charles Pfleeger &amp; Shari Lawrence Pfleeger, fourth Edition, PEARSON.<\/li>\n<li>Network Security by Charlie Kaufman, Radia Perlman, Mike Speciner, second Edition, PHI.<\/li>\n<li>The Complete Reference \u2013 Network Security by Roberta Bragg, Mark Rhodes-Ousley &amp; Keith Strassberg, Tata McGraw Hill<\/li>\n<li>Network Security Bible by Eric Cole, Ronald Krutz, James Conley, Wiley<\/li>\n<li>Hacking 6 Exposed by Stuart McClure, Joel Scambray &amp; George Kurtz , Tata McGraw Hill .<\/li>\n<li><a href=\"http:\/\/www.snort.org\/\">www.snort.org<\/a><\/li>\n<li><a href=\"https:\/\/nmap.org\/\">https:\/\/nmap.org<\/a><\/li>\n<\/ol>\n","protected":false},"author":4,"menu_order":9,"template":"","meta":{"pb_show_title":"on","pb_short_title":"","pb_subtitle":"","pb_authors":["miss-hiteishi-diwanji"],"pb_section_license":""},"chapter-type":[],"contributor":[58],"license":[],"class_list":["post-101","chapter","type-chapter","status-publish","hentry","contributor-miss-hiteishi-diwanji"],"part":3,"_links":{"self":[{"href":"https:\/\/ebooks.inflibnet.ac.in\/itp4\/wp-json\/pressbooks\/v2\/chapters\/101","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/ebooks.inflibnet.ac.in\/itp4\/wp-json\/pressbooks\/v2\/chapters"}],"about":[{"href":"https:\/\/ebooks.inflibnet.ac.in\/itp4\/wp-json\/wp\/v2\/types\/chapter"}],"author":[{"embeddable":true,"href":"https:\/\/ebooks.inflibnet.ac.in\/itp4\/wp-json\/wp\/v2\/users\/4"}],"version-history":[{"count":4,"href":"https:\/\/ebooks.inflibnet.ac.in\/itp4\/wp-json\/pressbooks\/v2\/chapters\/101\/revisions"}],"predecessor-version":[{"id":437,"href":"https:\/\/ebooks.inflibnet.ac.in\/itp4\/wp-json\/pressbooks\/v2\/chapters\/101\/revisions\/437"}],"part":[{"href":"https:\/\/ebooks.inflibnet.ac.in\/itp4\/wp-json\/pressbooks\/v2\/parts\/3"}],"metadata":[{"href":"https:\/\/ebooks.inflibnet.ac.in\/itp4\/wp-json\/pressbooks\/v2\/chapters\/101\/metadata\/"}],"wp:attachment":[{"href":"https:\/\/ebooks.inflibnet.ac.in\/itp4\/wp-json\/wp\/v2\/media?parent=101"}],"wp:term":[{"taxonomy":"chapter-type","embeddable":true,"href":"https:\/\/ebooks.inflibnet.ac.in\/itp4\/wp-json\/pressbooks\/v2\/chapter-type?post=101"},{"taxonomy":"contributor","embeddable":true,"href":"https:\/\/ebooks.inflibnet.ac.in\/itp4\/wp-json\/wp\/v2\/contributor?post=101"},{"taxonomy":"license","embeddable":true,"href":"https:\/\/ebooks.inflibnet.ac.in\/itp4\/wp-json\/wp\/v2\/license?post=101"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}