home *** CD-ROM | disk | FTP | other *** search
/ Phoenix Rising BBS / phoenixrising.zip / phoenixrising / vir-docs / nk-info6.arj / NK-INFO6.011 < prev    next >
Text File  |  1993-05-05  |  6KB  |  113 lines
  1. ================================================================================
  2. Volume 1, Issue 6, May 1993
  3. NuKE Info-Journal #6
  4.  
  5.             NuKE-NuKE-NuKE-NuKE-NuKE-NuKE-NuKE-NuKE-NuKE-NuKE-NuKE
  6.             uK                                                  E-
  7.             KE    "Rivest, Shamir, Adleman, (RSA) Encryption"   -N
  8.             E-                                                  Nu
  9.             -N                                                  uK
  10.             Nu                       By                         KE
  11.             uK                   Rock Steady                    E-
  12.             KE                                                  -N
  13.             E-NuKE-NuKE-NuKE-NuKE-NuKE-NuKE-NuKE-NuKE-NuKE-NuKE-Nu
  14.           
  15.  
  16. Ahh, the last NuKE Informational Journal #5, concerning DES Encryption brought
  17. about a fair amount of generous reviews. It has even inspired me to continue 
  18. this topic of `Digital Security' hence forth I introduce to you RSA. Rivest,
  19. Shamir, Adlemen (RSA) are the three mathematicians whom have patented the idea
  20. of `Public-Key' encryption, which by far isn't `just another' encryption 
  21. method. 
  22.  
  23. Public-Key crypto-systems are often referred to as `asymmetric' crypto-systems. The
  24. now famous DES is of a form of `symmetric' crypto-systems. Symmetric, consists
  25. the use of a single key for decrypting and encrypting. Asymmetric on the other
  26. hand, consists of two keys; a public key used to encrypt, and a private key 
  27. used to decrypt the cipher. (Cipher, is data that is encrypted)
  28.  
  29. RSA algorithm work on the idea that prime numbers cannot be broken into a 
  30. product of smaller factors. The algorithms work like so; first pick a number
  31. N that is the product of two prime numbers (call the two primes a and b so
  32. that N = a x b). Next, pick a number that will become your public key, and 
  33. call it P; P _must_ be less than N. Now to encrypt a message M, you simple
  34. apply the following formula:
  35.  
  36. C=M^P(mod N)
  37.  
  38. % What the hells `mod'? %
  39.  
  40. Public-key crypto-systems depend heavily on a number theory known as modular
  41. arithmetic or finite math. "Mod" can be said to be a remainder of a number. 
  42. 13 mod 5 = 3, since that's the remainder when 13 is divided by 5. But the 
  43. theory of Modular Math contains a pattern, a range, depending on the modular
  44. numbers. The modular of 50, are numbers from 0, 1, 2, ..., 49; the smallest 
  45. being 0, and the largest is the modulus number minus 1. 
  46.  
  47. A less formal and probably easier-to-visualise is called the `clock arithmetic'
  48. If you restrict yourself to performing math by moving the hour hand clockwise 
  49. (addition) or counterclockwise (subtraction) around the face of a clock, you'll
  50. soon see obvious patterns. Mostly, no matter how complex the math is, your 
  51. answer will _always_ be some number in the range of 1 to 12, which are the 
  52. number of hours on a standard clock. This actually is the basis of `finite' 
  53. mathematics, whereby you are always working with integers and you're always
  54. working with a finite set of integers. 
  55. Therefore, results of addition, subtraction, multiplication and division 
  56. will _always_ land in the set defined by the modulus. (huh? how can that be?)
  57. As with the clock theory, the numbers "wrap around", meaning if the modular of
  58. 50 is a set of integers from 0 -> 49, once we reach 49 (the largest number) and
  59. add 1, we would get 0. The number 49 will wrap around to 0, and the reverse is 
  60. true (0 wraps around to 49). 
  61.  
  62. The great think about modular math, is that it's finite, you don't have to worry
  63. about calculations yielding numbers that grow out of control, and also, since
  64. we are working with integers, you don't lose any information through round-off
  65. errors as you would with floating-point. 
  66.  
  67. Back to our formula;
  68.  
  69. C=M^P(mod N)
  70.  
  71. where C is the encrypted message, notice the message will be represented as
  72. numbers, you can use the ASCII value of each characters. See it's not hard to 
  73. find two large prime numbers (a and b) but if I hand you their product (N), you
  74. will perhaps never find a and b again! So in RSA, you get a huge 512-1024 bit 
  75. prime number which is the product of two large primes, a and b. The number N is 
  76. made public, while a and b remains secret. And after the formula is completed 
  77. the encrypted message cannot be cracked without factoring N!  
  78.  
  79. Now to decrypt the message we use the some-what same formula with different
  80. factors;
  81.  
  82. M=C^p(mod N) (Note: This is lower case `p')
  83.  
  84. where `p' (lower case) is the secret key. The secret key is calculated using 
  85. the formula;
  86.  
  87. P x p = 1(mod L)
  88.  
  89. where L is the least common multiple of (a-1) and (b-1). In mathematical 
  90. terminology, `p' is the multiplicative inverse of `P' in the modulus L. 
  91. Algorithms are available for computing least common multiples and 
  92. multiplicative inverses in modular arithmetic. You can look-up theses formulas
  93. for more understanding in almost any good college mathematic book, as I cannot
  94. teach you math in a matter of paragraphs. But I suspect most of the readers
  95. already know such basic mathematical skills.
  96.  
  97. Anyhow, RSA has undergone quite a bit of research around its algorithm. 
  98. Breaking the system requires the determination of `a' and `b', which are
  99. the factors of `N' (don't forget `N' and `P' are publicly known). Once you
  100. know `a' and `b', the factors of `N', you can easily calculate L. Knowing L
  101. and P, you can calculate `p' (lower case), and decrypt the ciphertext. This
  102. boils down to the task of factoring a number into its prime components, an
  103. ongoing popular problem in number theory that continues to occupy the minds
  104. and computers of mathematicians around the world. 
  105.  
  106. In October 1988, it took an international group of computer scientists nearly
  107. a month to factor a 100-digit number. More than 400 computers worked on the 
  108. problem during idle hours to find the number's two factors. One 41 digits long,
  109. the other 60 digits long. In June 1990, another team factored a 155-digit 
  110. number. The number was hand-picked to make the task easier, but it still took
  111. 275 years worth of ONE computer's time. To keep pace with even-faster computers
  112. RSA's inventors can simply add more digits to the system's key. 
  113. ================================================================================