ࡱ> .0-` jbjb $ dd N6 6 6 6 J N j n n n n n n n N P P P P P P , R#| n n n n n | N n n N N N n pn n N N ,@ n N N N N ^ -~36 pN N 0 N N N N NNdNNA step-by-step explanation of public-key cryptography Receiver 1. Pick very large primes p and q and compute n = pq. 2. Compute the least common multiple of p 1 and q 1; let us call it m. 3. Pick r relatively prime to m. 4. Find s such that rs mod m = 1. 5. Publicly announce n and r. Sender 1. Convert your message to a string of digits. 2. Break up the message into uniform blocks of digits; call them M1, M2,, Mk. 3. Check to see that greatest common divisor of each Mi and n is 1. If not, n can be factored and our code is broken. (In practice, the primes p and q are so large that they exceed all Mi, so this step may be omitted.) 4. Calculate and send Ri = Mir mod n. Receiver 1. For each received message Ri, calculate RiS mod n. 2. Convert the string of digits back to a string of characters. An example of public-key cryptography p = 53 m = 1508 r = 5 q = 59 n = 3127 For this example, we will attempt to securely transmit the very short message MATH. We first convert the text into a string of digits by replacing A by 01, B by 02,, Z by 26, and a blank by 00. So our message becomes 13012008. To keep things simple, we will send the message in blocks of four digits. The receiver of the message has picked two primes p and q, in this example we will use 53 and 59, and an integer r that has no prime divisors in common with lcm(p 1, q 1) = 1508, say 5, and has published n = 53 59 = 3127 and r = 5. We will send the encrypted message in the form of two blocks of numbers, 13015 mod 3127 and 20085 mod 3127, and the receiver will unscramble them. 13015mod 3127 = 361 And so the number 361 is sent to the receiver to represent the first two characters, and the number 386 is sent to the receiver to represent the second two characters (arithmetic not shown). To convert these numbers back to 1301 and 2008 respectively, the receiver takes the two factors of 3127 and calculates the least common multiple of p 1 = 52 and q 1 = 58, which is 1508 (this is where knowledge of p and q is necessary). Next the receiver must find s = r-1 in U(1508)that is, solve the equation 5 s = 1 mod 1508. This number is 905. Then the receiver takes the number received, 13, and calculates 386905 mod 3127, which is 1301, the first half, MA, of our original message. Similar calculations on 386 reveal the second half of the message to be TH. Without knowing how pq factors, one cannot find the modulus (in our case, 1508) that is needed to determine the intended message. Of course, for the sake of simplicity I have here used a much smaller key number than is generally used. It would be quite possible to determine p and q from this example, but such is not the case when p and q are very, very large. Example adapted from: Gallian, Joseph A. Contemporary Abstract Algebra. New York: Houghton Mifflin Company. 7?Z[`anort #*78=>`abc) ͺͺh7 h7 CJH*h7 h7 CJh7 h7 CJH*hQh7 6CJhQh7 CJhQh7 5CJhQh7 5>*CJI67@v"#*Y) * + Q R } ~ . / C  P gd7 gd7 $a$gd7 ) R S Z [ d e k l s t   M N T V | } 3 4 BCSURSXYh7 h7 h7 CJh7 h7 CJH*hQh7 CJhQh7 6CJhQh7 5>*CJ>C D `gd7 gd7  P gd7 ":p7 / =!"#$%<@< NormalCJaJmH sH tH DA@D Default Paragraph FontRiR  Table Normal4 l4a (k(No ListD@D 7 Balloon TextCJOJQJaJ4+@4 7 Endnote Text>*@> 7 Endnote ReferenceH*  !z 67@v"#*Y)*+QR}~./CD    00ˀ0ˀ0ˀ0ˀ0ˀ0ˀ0ˀ0ˀ0ˀ0ˀ0p0p00ˀ0ˀ00ˀ0ˀ0ˀ0ˀ0ˀ0О0ˀ0p0ˀ0p0ˀ00ˀ0ˀ0ˀ0О00pʀ 80P0o67@v"#*Y)*+QR}~./CD   0@0@0@0A0A0A0A0A0A0A0A 0A 0A 0A0A000000000P50 lP50 lP50 lP50 lP50 lP50 lP50 lP50 lP50 l gd0 n )  C    rtS U   rtRS$IMS U *   :::::::@ %Q mW @UnknownGTimes New Roman5Symbol3 ArialC΀w_Lucida Grande 1hܔfO;F't 4 .@(q)5A mathematical explanation of public-key cryptographyA HA H Oh+'0  $ @ L Xdlt|'6A mathematical explanation of public-key cryptography=0A H HNormalA H39Microsoft Word 11.0@{4@ÌK@j B GPICTb HHb bHHc)bbb           [&VckZg9Vg9sVg9^g9g9^RZZkZF1Zg9^JRkZVVg9g9cg9g9^kZZ^g9Z^Vg9  Vg9RZg9g9 OkZZo{g9^g9g9ZRkZ^RkZJRg9g9^Vc^^Vg9^Ns^kZg9Zc^c k.ZV^Ns^^ZkZZg9Z^Zg9^NsNs^^Ns^kZ^kZg9^g9^o{kZ^^Vco{kZkZg9Rg9RkZo{kZVw 3cZo{g9^kZg9R^g9g9Z^^Nsg9RV 5cZVVg9^g9ZR^kZZNs^VVckZ+cZ^V^Ns^JRZ^^Ns   Rg9ZJRg9 EkZV^^g9ZkZg9^^F1g9g9R^g9R^g9kZ^^^Nso{Nsg9 qZF1kZg9^+Rg9Nsg9g9^^g9VR^^Z^kZNsVRg9R^g9VVo{Zg9^kZkZZg9NsV^wVVwVkZkZ "cVZg9g9F1g9g9g9R^RkZg9Rg9Zg9F1Ns^^VZZ^kZ^g9^g9ZV^F1ZkZkZR^g9Zg9^^JRg9^JRkZg9V^^V^^Z^Vg9Z VkZ^^g9^kZkZ^R^JRNsg9^kZJRg9g9^ Vc^Zg9^RkZ^ZZ^kZZg9JRkZkZVNs^RZg9Z^Ns^g9Vg9^Nso{kZg9VkZ;cV^Z^RkZg9^^JRg9^VRcVcNs^VZo{o{  Vg9RZg9g9g9O kZZ^kZg9^NskZg9g9Zg9VNsg9g9R^g9RkZg9Rg9RRg9Ro{Ns^VZ T!ZV^^g9ZRg9g9kZV^^g9VV^g9VR^R^g9kZV^^g9g9Z^Z    GVZg9g9Zo{Rg9ZR^NsVVg9g9cg9g9^kZZ^g9Z^Vg9   E^cVckZcVVkZcccVZcckZZc   Z^kZRZg9g9^F1Zwcg9cF1kZg9Ns^Rg9(JRZkZ^^g9Nso{Rg9g9kZg9g9Z^F1kZg9g9^^NskZ^^RZZg9^Zg9^^g9ZRg9(Zg9^^R^g9kZV^^g9VVo{ZVg9kZg9RRV^^Vg9VkZBVg9VVwVVg9Z^V^Ns^VNsVZ^^^F1g9g9^^g9 &Vg9g9F1g9g9kZcVkZZVVJR^^g9g9^RV^g9o{Ns^Z^g9co{Zg9^VRg9Nsg9^RVVRg9R^g9g9^^NsVo{Z^Zg9kZg9g9Zg9kZ ^g9Rg9Nsg9RJRg9^Z^g9VV^^kZJRg9g9^(VcRRo{g9g9RNs^kZg9cg9co{kZ^g9cc^^VcVZ^V^^VkZg9^ZkZR^kZ Z^g9^3F1g9VZo{g9^kZg9JR^NsNs^^cJRZNsRo{kZ^^VkZJRVwg9^RZ^VZR^^VRZg9VZco{cVco{DckZZc^^NsccZo{g9c^Zg9^VRg9g9^g9kZg9JRZNsg9g9^^g9VRg9g9^kZNs^g9V^VRg9^g9^g9^^NsVNswkZcVkZNs^VckZZco{Y%^^VZVVB^VckZZcZ^VJRkZg9g9Rg9kZco{kZ^^g9RNsVkZZZg9Ns  ) kZcV^Ns^VckZZcZkZ   A^^Vg9^Rg9^^NsVZcZkZZg9g9^RRg9kZg9g9Zg9kZRkZg9^kZg9^kZZg9g9^F1^Ns^kZRZkZc^^VRg9^^NsVg9VVZZ >g9g9BRZg9g9Rg9kZRkZg9JRg9RRg9g9g9g9^^F1^g9ZRRZkZZ^kZJRNsg9^g9^^ZZ^c^kZ^^g9^^g9Bg9g9g9 B^^NsVg9kZRJR^RkZcVR^VZVVNsg9Rg9g9Rg9ZwRg9kZg9g9Zg9kZR^g9g9Rg9V^g9^JRkZg9^g9ckZZNs^Vg9^Z^RZg9Rg9 2Z^Zg9^NsNs^^Ns^kZVkZg9^R^ccZ^^Vco{kZccRcZo{g9ZZkZcVNsRo{^g9cZg9Z^ cZV^g9^R^^VcZ^g9=^kZJRZg9Rg9kZg9g9Zg9kZNs^Zg9VVg9ckZo{VVkZkZcVNscR^^cg9^Zg9Rg9g9^^F1^co{g9ckZNs^VkZcVV @^ZZ^^NsVg9kZZVVNsZg9^kZZg9Zg9Rg9kZkZ^^g9Rg9^^NsVg9kZg9g9o{g9g9Vg9cZ^VRZ^RZg9cVZg9F1VVckZZcw cZ(kZcVkZNsg9^g9kZZ^VkZ^Zg9^^kZ^RV^kZNsg9g9^^g9ZJR^kZg9^ZR^ g9^^cVZkZg9g9RkZNsg9^^V Z^Z^Zg9Nsg9 RRVg9^RZo{R^^R^^cV^Z^c^cg9^Z^kZg9Z^g9^kZg9VVRg9Ns^V^Rg9kZV^^kZRg9c BkZcVVkZR^R^g9g9Vg9VRJRZkZNsVg9kZZg9VZ^Vg9Bg9g9^RJRg9R^kZg9g9c^Rg9g9^R^g9g9JR^kZZRR^g9Nsg9kZg9 *^g9g9JRNs^g9Zg9Ns^ZkZ^g9g9^^NsJRkZR^^ZR^g9RkZg9^g9g9NskZc^^NsVg9^g9^^g9NsZkZ^Vg9ZF1Vg9^^JRc ig9kZ^NsNsg9^F1kZcV^Z^g9ZZ^^Rg9g9^g9cZg9^Vc^Zg9g9kZg9cg9kZJRkZ^g9        (VkZ^JRkZc^Z^F1Zg9kZcVNs^kZRZwg9Rc^VcR^^ZNs^^kZ^kZRVg9kZRg9VkZ^Zc^g9V^wNscc^VRF1sZF1 ZcV^^Zcw                     ՜.+,0 `hpx  '  6A mathematical explanation of public-key cryptography Title  !"#$&'()*+,/Root Entry F(A11TableWordDocument$ SummaryInformation(DocumentSummaryInformation8%CompObjX FMicrosoft Word DocumentNB6WWord.Document.8