Section 2.4 Mathematical Foundation
Cryptography relies largely on the concept of one-way or trap door functions. That is a process that is hard to compute in one direction, but easy to compute in the other. For example it is much easier for a computer to multiply large numbers than to determine the factors of large numbers. This is the foundation of the RSA algorithm. A simplified version of the algorithm is shown below:
1
www.cs.drexel.edu/~jpopyack/IntroCS/HW/RSAWorksheet.htmlKEY GENERATION
p = a random prime number
q = a random prime number
N = p * q
r = (p - 1) * (q - 1)
K = a number which equals one when modded by r and can be factored
e = a factor of K that doesn't share factors with N
d = another factor of K that doesn't share factors with N
Your public key is N and e
Your private key is N and d
ENCRYPTION
ciphertext = (cleartext**e)%N
DECRYPTION
cleartext = (ciphertext**d)%N
EXAMPLE
p = 7
q = 13
N = 7 * 13 = 91
r = 72
K = 145 (because 145%72 = 1)
e = 5
d = 29
Public Key = 91, 5
Private Key = 91, 29
cleartext = 72 ('H' in ASCII)
ciphertext = (72**5)%91 = 11 (encrypted using N and e)
cleartext = (11**29)%91 = 72 (decrypted using N and d)
In order to crack RSA you would need to be able to factor N into its two prime numbers. While it is trivial in our simple example, imagine how difficult it would be to factor a number with 1400 decimal digits, the current recommended keysize for RSA. You’ll notice that the algorithm only requires exponentiation, multiplication, and modulus arithmetic. At no point do you ever have to factor a large prime number to generate keys, encrypt, or decrypt. You only have to perform that operation if you’re trying to work backwards without the keys.
2
stackoverflow.com/questions/11832022/why-are-large-prime-numbers-used-in-rsa-encryptionOther similar one-way function exist based on elliptical curves. It turns out that motion along an elliptical curve can be described according to a start and end point and several iterations of a simple algorithm. You can reconstruct the initial conditions if you know the start point, end point, and how many iterations it took. If all you know is the start and end point you can’t determine the initial conditions.
You have attempted 1 of 1 activities on this page.
