Global AI and Data Science

Global AI & Data Science

Train, tune and distribute models with generative AI and machine learning capabilities

 View Only

RSA Cryptography

By Moloy De posted Thu February 06, 2020 08:50 PM

  
‘Data Security’ / ‘Data Integrity’ are the modern day buzz words that we need to keep an eye on when working with data. Cryptography plays a havoc role here. RSA Algorithm, emerged in 1978, plays the basic role in advancement of modern day cryptography, often referred as Public Key Cryptography.

RSA stands for Ron Rivest, Adi Shamir and Leonard Adleman, who first publicly described the encryption algorithm in 1978. A user of RSA creates and then publishes the product of two large prime numbers, along with an auxiliary value, as their public key. Anyone can use the public key to encrypt a message, but with currently published methods, if the public key is large enough, only someone with knowledge of the respective private key can feasibly decode the message.

A working example:

  1. Choose two random prime numbers, say p = 61 and q=53
  2. Compute n = pq = 61*53 = 3233
  3. Compute the Totient φ(n) = (p-1)(q-1) = (61 - 1)(53 - 1) = 3120
  4. Choose e>1 coprime to 3120, say e = 17
  5. Choose d, to satisfy de = 1 mod( φ(n) ), say d = 2753
  6. Observe 17 * 2753 = 46801 = 1 + 15 * 3120
  7. The public key is (n=3233, e=17)
  8. To encrypt say m=123
  9. One calculates c = me mod(n) = 12317 mod(3233) = 855 and the value of c is sent to the receiver
  10. The private key is (n=3233, d=2753)
  11. To decrypt c = 855, receiver calculates cd mod(n) = 8552753 mod(3233) = 123 which is the retrieved value of m


The theory behind:

  1. φ(n) is the Euler's Totient Function that counts the positive integers below n that are Coprime to n
  2. For a prime p, φ(p) = p-1
  3. For two positive integers a and b, φ(ab) = φ(a) φ(b)
  4. So, for two primes p and q, φ(pq) = (p-1) (q-1)
  5. Now, de = 1 mod(φ(n)) = 1 mod((p-1)(q-1))
  6. So, de = 1 mod(p-1) also de = 1 mod(q-1)
  7. By Fermat’s Little Theorem, mde = m mod(p), mde = m mod(q)
  8. Since p and q are distinct prime numbers, applying Chinese Remainder Theorem, mde = m mod(pq) = m mod(n)
  9. So, cd = mde = m mod(n)
Question 1: RSA Cryptography will be useless with the advent of Quantum Computing. Why?

Question 2: Is Prime factorization NP Hard?
#GlobalAIandDataScience
#GlobalDataScience
1 comment
79 views

Permalink

https://community.ibm.com/community/user/blogs/moloy-de1/2020/02/06/rsa-cryptography

Comments

Data Cryp
Fri May 01, 2020 08:05 PM

The Process hollowing and Portable Executable (PE) Injection technique enables us to inject and run a complete executable module inside another process memory. this Crypter feature help hacker to run a malicious file

Crypter maker uses Process unload to get more FUD time. So the most important of FUD crypter is RunPE. This trick has been used much time in the malware industry, especially in RATs (Remote Administration Trojans). Data Encoder uses a powerful unhooked RunPE which can inject codes/files (malicious/pure codes) into legit processes. It is useful to bypass any proactive on runtime.