{"id":128,"date":"2018-07-11T11:44:33","date_gmt":"2018-07-11T11:44:33","guid":{"rendered":"http:\/\/itp4.epgpbooks.inflibnet.ac.in\/?post_type=chapter&#038;p=128"},"modified":"2019-05-13T12:34:01","modified_gmt":"2019-05-13T12:34:01","slug":"random-number-generation","status":"publish","type":"chapter","link":"https:\/\/ebooks.inflibnet.ac.in\/itp4\/chapter\/random-number-generation\/","title":{"rendered":"Random Number Generation"},"content":{"raw":"<div><span style=\"float: right;\"><a href=\"https:\/\/youtu.be\/i7vpmIDcD4w\" 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<div>\r\n\r\nBlum Blum Shub Generator(Cryptographically secure psuedorandom bit generator):\r\n\r\n&nbsp;\r\n\r\n\u00a8\u00a0 based on public key algorithms\r\n\r\n\u00a8\u00a0 use least significant bit from iterative equation x<em>i<\/em> <em>= x<\/em><em>i-1<\/em><em>2<\/em> <em>mod n<\/em>\r\n\r\n\u00a8\u00a0\u00a0 where n=p.q, and primes p\u2261q\u22613 mod 4\r\n\r\n\u00a8\u00a0\u00a0 unpredictable, passes <strong>next-bit test<\/strong>\r\n\r\n\u00a8\u00a0\u00a0 security rests on difficulty of factoring n\r\n\r\n\u00a8\u00a0\u00a0 is unpredictable given any run of bits\r\n\r\n\u00a8\u00a0\u00a0 slow, since very large numbers must be used\r\n\r\n\u00a8\u00a0\u00a0 too slow to use for cipher use, good for key generation\r\n\r\n&nbsp;\r\n\r\nExample Blum Blum Shub Generator:\r\n\r\n&nbsp;\r\n\r\n\u00a8\u00a0 n=192649=383x503\r\n\r\n\u00a8\u00a0\u00a0 Seed s=101355\r\n\r\n&nbsp;\r\n<table class=\"aligncenter\" border=\"1\">\r\n<tbody>\r\n<tr>\r\n<td style=\"width: 270.063px\">i<\/td>\r\n<td style=\"width: 255.063px\">Xi<\/td>\r\n<td style=\"width: 121.063px\">Bi<\/td>\r\n<\/tr>\r\n<tr>\r\n<td style=\"width: 270.063px\"><\/td>\r\n<td style=\"width: 255.063px\"><\/td>\r\n<td style=\"width: 121.063px\"><\/td>\r\n<\/tr>\r\n<tr>\r\n<td style=\"width: 270.063px\">0<\/td>\r\n<td style=\"width: 255.063px\">20749<\/td>\r\n<td style=\"width: 121.063px\"><\/td>\r\n<\/tr>\r\n<tr>\r\n<td style=\"width: 270.063px\"><\/td>\r\n<td style=\"width: 255.063px\"><\/td>\r\n<td style=\"width: 121.063px\"><\/td>\r\n<\/tr>\r\n<tr>\r\n<td style=\"width: 270.063px\">1<\/td>\r\n<td style=\"width: 255.063px\"><\/td>\r\n<td style=\"width: 121.063px\">1<\/td>\r\n<\/tr>\r\n<tr>\r\n<td style=\"width: 270.063px\">143135<\/td>\r\n<\/tr>\r\n<tr>\r\n<td style=\"width: 270.063px\"><\/td>\r\n<td style=\"width: 255.063px\"><\/td>\r\n<td style=\"width: 121.063px\"><\/td>\r\n<\/tr>\r\n<tr>\r\n<td style=\"width: 270.063px\">2<\/td>\r\n<td style=\"width: 255.063px\">177671<\/td>\r\n<td style=\"width: 121.063px\">1<\/td>\r\n<\/tr>\r\n<tr>\r\n<td style=\"width: 270.063px\"><\/td>\r\n<td style=\"width: 255.063px\"><\/td>\r\n<td style=\"width: 121.063px\"><\/td>\r\n<\/tr>\r\n<tr>\r\n<td style=\"width: 270.063px\">3<\/td>\r\n<td style=\"width: 255.063px\">97048<\/td>\r\n<td style=\"width: 121.063px\">0<\/td>\r\n<\/tr>\r\n<tr>\r\n<td style=\"width: 270.063px\"><\/td>\r\n<td style=\"width: 255.063px\"><\/td>\r\n<td style=\"width: 121.063px\"><\/td>\r\n<\/tr>\r\n<\/tbody>\r\n<\/table>\r\n&nbsp;\r\n\r\n&nbsp;\r\n\r\n<strong>Fermat's Theorem<\/strong>\r\n\r\n<\/div>\r\n\u00a8 ap-1 = 1 (mod p)\r\n<ul>\r\n \t<li>\u00a8 where p is prime and gcd(a,p)=1<\/li>\r\n \t<li>\u00a8 also ap = p (mod p)<\/li>\r\n \t<li>\u00a8 useful in public key and primality testing<\/li>\r\n<\/ul>\r\n<strong>Euler's Theorem<\/strong>:\r\n<ul>\r\n \t<li>\u00a8 a generalisation of Fermat's Theorem a\u00f8(n) = 1 (mod n)<\/li>\r\n \t<li>\u00a8 for any a,n where gcd(a,n)=1<\/li>\r\n \t<li>\u00a4 <em>a=3;n=10; \u00f8(10)=4;<\/em><\/li>\r\n<\/ul>\r\nhence 34 = 81 = 1 mod 10\r\n<ul>\r\n \t<li>\u00a4 <em>a=2;n=11; \u00f8(11)=10;<\/em><\/li>\r\n<\/ul>\r\nhence 210 = 1024 = 1 mod 11\r\n\r\n&nbsp;\r\n\r\n<strong>Primality Testing<\/strong><strong>:<\/strong>\r\n<ul>\r\n \t<li>\u00a8 divide by all numbers (primes) in turn less than the square root of the number<\/li>\r\n \t<li>\u00a8 only works for small numbers<\/li>\r\n \t<li>\u00a8 alternatively can use statistical primality tests based on properties of primes<\/li>\r\n \t<li>1) for which all primes numbers satisfy property.<\/li>\r\n \t<li>2) some composite numbers, also satisfy the property.<\/li>\r\n<\/ul>\r\nMiller Rabin Algorithm- a test based on Fermat\u2019s Theorem:\r\n<ul>\r\n \t<li>\u00a8 algorithm is:<\/li>\r\n<\/ul>\r\n<ol>\r\n \t<li>1.\u00a4 TEST (<em>n) is:<\/em><\/li>\r\n \t<li>Find integers <em>k, q, k &gt; 0, q odd, so that (n\u20131)=2<\/em><em>k<\/em><em>q<\/em><\/li>\r\n \t<li>Select a random integer <em>a, 1&lt;a&lt;n\u20131<\/em><\/li>\r\n \t<li><strong>if <em>a<\/em><\/strong><strong><em>q<\/em><\/strong><strong> <em>mod n = 1 then return (\u201cmaybe prime\");<\/em><\/strong><\/li>\r\n \t<li><strong>for <em>j = 0 to k<\/em> <em>\u2013<\/em> <em>1 do<\/em><\/strong><\/li>\r\n \t<li><strong>if (<em>a<\/em><\/strong><strong><em>2jq<\/em><\/strong><strong> <em>mod n = n-1)<\/em><\/strong><\/li>\r\n<\/ol>\r\n<strong>then return(\" maybe prime \")<\/strong>\r\n<ol start=\"6\">\r\n \t<li>return (\"composite\")<\/li>\r\n<\/ol>\r\n<strong>Applying Miller Rabin Algorithm:<\/strong>\r\n<ul>\r\n \t<li>\u00a8 n=29<\/li>\r\n \t<li>\u00a8 n-1=28=22x7=2kqa=10<\/li>\r\n \t<li>\u00a8 107 mod 29=17 neither 1 nor 28.<\/li>\r\n \t<li>\u00a8 (107)2 mod 29=28<\/li>\r\n \t<li>\u00a8 Returns inconclusive(29 may be prime) Try again a=2<\/li>\r\n \t<li>\u00a8 27 mod 29=12 neither 1 nor 28.<\/li>\r\n \t<li>\u00a8 214 mod 29=28<\/li>\r\n \t<li>\u00a8 Returns inconclusive(29 may be prime)<\/li>\r\n<\/ul>\r\n\r\n<table>\r\n<tbody>\r\n<tr>\r\n<td><strong>you can view video on Random Number Generation<\/strong><\/td>\r\n<td><a href=\"https:\/\/youtu.be\/i7vpmIDcD4w\" 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 style=\"text-align: initial;font-size: 1em\" href=\"https:\/\/nmap.org\/\">https:\/\/nmap.org<\/a><\/li>\r\n<\/ol>","rendered":"<div><span style=\"float: right;\"><a href=\"https:\/\/youtu.be\/i7vpmIDcD4w\" 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<div>\n<p>Blum Blum Shub Generator(Cryptographically secure psuedorandom bit generator):<\/p>\n<p>&nbsp;<\/p>\n<p>\u00a8\u00a0 based on public key algorithms<\/p>\n<p>\u00a8\u00a0 use least significant bit from iterative equation x<em>i<\/em> <em>= x<\/em><em>i-1<\/em><em>2<\/em> <em>mod n<\/em><\/p>\n<p>\u00a8\u00a0\u00a0 where n=p.q, and primes p\u2261q\u22613 mod 4<\/p>\n<p>\u00a8\u00a0\u00a0 unpredictable, passes <strong>next-bit test<\/strong><\/p>\n<p>\u00a8\u00a0\u00a0 security rests on difficulty of factoring n<\/p>\n<p>\u00a8\u00a0\u00a0 is unpredictable given any run of bits<\/p>\n<p>\u00a8\u00a0\u00a0 slow, since very large numbers must be used<\/p>\n<p>\u00a8\u00a0\u00a0 too slow to use for cipher use, good for key generation<\/p>\n<p>&nbsp;<\/p>\n<p>Example Blum Blum Shub Generator:<\/p>\n<p>&nbsp;<\/p>\n<p>\u00a8\u00a0 n=192649=383&#215;503<\/p>\n<p>\u00a8\u00a0\u00a0 Seed s=101355<\/p>\n<p>&nbsp;<\/p>\n<table class=\"aligncenter\">\n<tbody>\n<tr>\n<td style=\"width: 270.063px\">i<\/td>\n<td style=\"width: 255.063px\">Xi<\/td>\n<td style=\"width: 121.063px\">Bi<\/td>\n<\/tr>\n<tr>\n<td style=\"width: 270.063px\"><\/td>\n<td style=\"width: 255.063px\"><\/td>\n<td style=\"width: 121.063px\"><\/td>\n<\/tr>\n<tr>\n<td style=\"width: 270.063px\">0<\/td>\n<td style=\"width: 255.063px\">20749<\/td>\n<td style=\"width: 121.063px\"><\/td>\n<\/tr>\n<tr>\n<td style=\"width: 270.063px\"><\/td>\n<td style=\"width: 255.063px\"><\/td>\n<td style=\"width: 121.063px\"><\/td>\n<\/tr>\n<tr>\n<td style=\"width: 270.063px\">1<\/td>\n<td style=\"width: 255.063px\"><\/td>\n<td style=\"width: 121.063px\">1<\/td>\n<\/tr>\n<tr>\n<td style=\"width: 270.063px\">143135<\/td>\n<\/tr>\n<tr>\n<td style=\"width: 270.063px\"><\/td>\n<td style=\"width: 255.063px\"><\/td>\n<td style=\"width: 121.063px\"><\/td>\n<\/tr>\n<tr>\n<td style=\"width: 270.063px\">2<\/td>\n<td style=\"width: 255.063px\">177671<\/td>\n<td style=\"width: 121.063px\">1<\/td>\n<\/tr>\n<tr>\n<td style=\"width: 270.063px\"><\/td>\n<td style=\"width: 255.063px\"><\/td>\n<td style=\"width: 121.063px\"><\/td>\n<\/tr>\n<tr>\n<td style=\"width: 270.063px\">3<\/td>\n<td style=\"width: 255.063px\">97048<\/td>\n<td style=\"width: 121.063px\">0<\/td>\n<\/tr>\n<tr>\n<td style=\"width: 270.063px\"><\/td>\n<td style=\"width: 255.063px\"><\/td>\n<td style=\"width: 121.063px\"><\/td>\n<\/tr>\n<\/tbody>\n<\/table>\n<p>&nbsp;<\/p>\n<p>&nbsp;<\/p>\n<p><strong>Fermat&#8217;s Theorem<\/strong><\/p>\n<\/div>\n<p>\u00a8 ap-1 = 1 (mod p)<\/p>\n<ul>\n<li>\u00a8 where p is prime and gcd(a,p)=1<\/li>\n<li>\u00a8 also ap = p (mod p)<\/li>\n<li>\u00a8 useful in public key and primality testing<\/li>\n<\/ul>\n<p><strong>Euler&#8217;s Theorem<\/strong>:<\/p>\n<ul>\n<li>\u00a8 a generalisation of Fermat&#8217;s Theorem a\u00f8(n) = 1 (mod n)<\/li>\n<li>\u00a8 for any a,n where gcd(a,n)=1<\/li>\n<li>\u00a4 <em>a=3;n=10; \u00f8(10)=4;<\/em><\/li>\n<\/ul>\n<p>hence 34 = 81 = 1 mod 10<\/p>\n<ul>\n<li>\u00a4 <em>a=2;n=11; \u00f8(11)=10;<\/em><\/li>\n<\/ul>\n<p>hence 210 = 1024 = 1 mod 11<\/p>\n<p>&nbsp;<\/p>\n<p><strong>Primality Testing<\/strong><strong>:<\/strong><\/p>\n<ul>\n<li>\u00a8 divide by all numbers (primes) in turn less than the square root of the number<\/li>\n<li>\u00a8 only works for small numbers<\/li>\n<li>\u00a8 alternatively can use statistical primality tests based on properties of primes<\/li>\n<li>1) for which all primes numbers satisfy property.<\/li>\n<li>2) some composite numbers, also satisfy the property.<\/li>\n<\/ul>\n<p>Miller Rabin Algorithm- a test based on Fermat\u2019s Theorem:<\/p>\n<ul>\n<li>\u00a8 algorithm is:<\/li>\n<\/ul>\n<ol>\n<li>1.\u00a4 TEST (<em>n) is:<\/em><\/li>\n<li>Find integers <em>k, q, k &gt; 0, q odd, so that (n\u20131)=2<\/em><em>k<\/em><em>q<\/em><\/li>\n<li>Select a random integer <em>a, 1&lt;a&lt;n\u20131<\/em><\/li>\n<li><strong>if <em>a<\/em><\/strong><strong><em>q<\/em><\/strong><strong> <em>mod n = 1 then return (\u201cmaybe prime&#8221;);<\/em><\/strong><\/li>\n<li><strong>for <em>j = 0 to k<\/em> <em>\u2013<\/em> <em>1 do<\/em><\/strong><\/li>\n<li><strong>if (<em>a<\/em><\/strong><strong><em>2jq<\/em><\/strong><strong> <em>mod n = n-1)<\/em><\/strong><\/li>\n<\/ol>\n<p><strong>then return(&#8221; maybe prime &#8220;)<\/strong><\/p>\n<ol start=\"6\">\n<li>return (&#8220;composite&#8221;)<\/li>\n<\/ol>\n<p><strong>Applying Miller Rabin Algorithm:<\/strong><\/p>\n<ul>\n<li>\u00a8 n=29<\/li>\n<li>\u00a8 n-1=28=22&#215;7=2kqa=10<\/li>\n<li>\u00a8 107 mod 29=17 neither 1 nor 28.<\/li>\n<li>\u00a8 (107)2 mod 29=28<\/li>\n<li>\u00a8 Returns inconclusive(29 may be prime) Try again a=2<\/li>\n<li>\u00a8 27 mod 29=12 neither 1 nor 28.<\/li>\n<li>\u00a8 214 mod 29=28<\/li>\n<li>\u00a8 Returns inconclusive(29 may be prime)<\/li>\n<\/ul>\n<table>\n<tbody>\n<tr>\n<td><strong>you can view video on Random Number Generation<\/strong><\/td>\n<td><a href=\"https:\/\/youtu.be\/i7vpmIDcD4w\" 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 style=\"text-align: initial;font-size: 1em\" href=\"https:\/\/nmap.org\/\">https:\/\/nmap.org<\/a><\/li>\n<\/ol>\n","protected":false},"author":4,"menu_order":13,"template":"","meta":{"_acf_changed":false,"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-128","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\/128","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":5,"href":"https:\/\/ebooks.inflibnet.ac.in\/itp4\/wp-json\/pressbooks\/v2\/chapters\/128\/revisions"}],"predecessor-version":[{"id":448,"href":"https:\/\/ebooks.inflibnet.ac.in\/itp4\/wp-json\/pressbooks\/v2\/chapters\/128\/revisions\/448"}],"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\/128\/metadata\/"}],"wp:attachment":[{"href":"https:\/\/ebooks.inflibnet.ac.in\/itp4\/wp-json\/wp\/v2\/media?parent=128"}],"wp:term":[{"taxonomy":"chapter-type","embeddable":true,"href":"https:\/\/ebooks.inflibnet.ac.in\/itp4\/wp-json\/pressbooks\/v2\/chapter-type?post=128"},{"taxonomy":"contributor","embeddable":true,"href":"https:\/\/ebooks.inflibnet.ac.in\/itp4\/wp-json\/wp\/v2\/contributor?post=128"},{"taxonomy":"license","embeddable":true,"href":"https:\/\/ebooks.inflibnet.ac.in\/itp4\/wp-json\/wp\/v2\/license?post=128"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}