Introduction to cryptography(RSA Cipher)

In this note I want to discuss some ideas from modern cryptography..

SuperComputer SuperComputer

Don't be intimidated by the size of the note...if you understand the ideas properly trust me it's worth it...you will learn about one of the most effective cipher systems still actively used today!!

Public-Key Cryptography:\textbf{Public-Key Cryptography:}In conventional cryptographic systems like the Caesar cipher,the sender and the receiver jointly have a secret key that is used for encryption and decryption.But in public-key cryptography two keys are used - an encryption key and a decryption key.Though these keys are related,there is no easy way to derive the decryption key from the encryption key.Thus the encryption key can be made public without compromising the decryption key.A major advantage of the public cryptosystem is that it is unnecessary for the senders and the receivers to exchange a key in advance of their decision to communicate with one another.

Rivest-Shamir-Adleman Cipher:\textbf{Rivest-Shamir-Adleman Cipher:}In 1977,Ronald Rivest,Adi Shamir and Leonhard Adleman proposed a public-key encryption system that uses elementary ideas from number theory.It's security depends on the assumption that in the current state of computer technology,factorization of composite numbers having large prime factors is so time consuming that it is almost unrealistic.

RSA RSA

Procedure:\textbf{Procedure:}At first the user of the RS system chooses a pair of very large distinct primes.Then the two numbers are multiplied to form a number n=pqn = pq called the enciphering modulus\text{enciphering modulus}.The factorization of this product is beyond all computational abilities.Next,they need to select a positive integer kk such that gcd(k,ϕ(n))=1\gcd(k,\phi (n))=1 called the enciphering exponent\text{enciphering exponent}.the pair (n,k)(n,k) is kept in a public profile(like a telephone directory) as the user's personal encryption key which allows anyone else to encrypt and send a message to this individual,but the primes pp and qq are unknown to everybody else.

prime prime

ALGORITHM:\textbf{ALGORITHM:}

Encryption:\textbf{Encryption:}

Step 1.\textbf{Step 1.}First each alphabet of the message to be sent is converted into a 2-digit number.A standard procedure for executing this is using the following assignment:

ascii ascii

Step 2.\textbf{Step 2.}It is aasumed that the message M<nM < n, where n is the enciphering modulus.Otherwise it is diffucult to distinguish M from any larger integer congruent to MM modulo n. If the message M is too long then it is broken into separate blocks of digits M1,M2,....MsM_1,M_2,....M_s of appropriate size and each is coded separately.

Step 3.\textbf{Step 3.}After looking up the intended recipient's encryption key (n,k(n,k in the public directory,the sender disguises the plaintext MM into the ciphertext rr,by raising M to the kk-th power and then taking modulo nn,that is, Mkr(modn)M^{k} \equiv r \pmod{n}. kk is selected such that gcd(k,ϕ(n))=1gcd(k,\phi(n))=1

Decryption:\textbf{Decryption:}

Step 1.\textbf{Step 1.}The authorized personnel deciphers the message by first determining the recovery exponent jj, for which kj1(modϕ(n))kj \equiv 1 \pmod{\phi(n)}

Since gcd(k,ϕ(n))=1gcd(k,\phi(n)) = 1,this linear congruence has a uniqee solution modulo ϕ(n)\phi(n).The Euclidean Algorithm produces jj as a solution xx to the equation kx+ϕ(n)y=1kx+\phi(n)y = 1. Note that the recovery exponent can only be obtained by someone who knows both kk and ϕ(n)=(p1)(q1)\phi(n) = (p-1)(q-1) and hence both pp and qq.The knowledge of any unauthorized third party is limited to the public key (n,k)(n,k).

Step 2.\textbf{Step 2.}Now if we calculate rjmodnr^{j} \mod n, we get, rj(Mk)jM1+ϕ(n)tMMϕ(n)t\ r^{j} \equiv (M^{k})^{j} \equiv M^{1+\phi(n)*t} \equiv M*M^{\phi(n)*t} M1tM(modn)\equiv M*1^{t} \equiv M \pmod n whenever gcd(M,n)=1gcd(M,n)=1.

In other words raising the plaintext number to the jj-th power and taking moduulo n recovers the plaintext.

It is to be noted that the assumption gcd(M,n)=1gcd(M,n)=1 was used to use Euler's theorem.In case they are not relatively prime, we can prove by similar argument that rjM(modp)r^{j} \equiv M \pmod p rjM(modq)r^{j} \equiv M \pmod q Since gcd(p,q)=1gcd(p,q)=1, we have rjM(modpq)r^{j} \equiv M \pmod{pq},that is rjM(modn)r^{j} \equiv M \pmod n!!

Step3.\textbf{Step3.}Convert the digital representation to the alphabetic one.

Example:\textbf{Example:}

Let us consider an unrealistically small example choosing 2 primes p=29p = 29 and q=53q=53.

The enciphering modulus is then n=2953=1537n = 29*53 = 1537 and ϕ(n)=2852=1456\phi(n) = 28*52 = 1456.

Since gcd(47,1436)=1gcd(47,1436)=1, we may choose k=47k=47 to be the enciphering exponent.It can be calculated that in this case the recovery exponent will be 3131.

Let the first block from the digital version of the plaintext be 131131,this encrypts to the ciphertext 13147570(mod1537)131^{47} \equiv 570 \pmod{1537}.But by using the recovery exponent j=31j = 31, we can decrypt this to 57031131(mod1537)570^{31} \equiv 131 \pmod{1537}.

This is the original digital form of the plaintext !!!

Applications:\textbf{Applications:}Banks(1024-bit),Facebook(1024-bit),Twitter(1024-bit),Ebay(1024-bit) all use the RSA cipher to protect our internet secrets!!The numbers in the brackets denote the number of digits of the enciphering modulus. A 768 bit key has recently been broken.

hack hack

Have fun encrypting :D ....i'll try to do a few more posts on modern ciphers next week

References:\textbf{References:}

1.1.Introduction to Algorithms by Cormen,Leiserson,Rivest and Stein

2.2.Elementary Number Theory by David M.Burton(I took the example from here)

3.3.Encryption and huge numbers by NumberPhile (Video by Brady Haran and demonstrated by Dr.James Grime)

Note by Eddie The Head
5 years, 7 months ago

No vote yet
1 vote

  Easy Math Editor

This discussion board is a place to discuss our Daily Challenges and the math and science related to those challenges. Explanations are more than just a solution — they should explain the steps and thinking strategies that you used to obtain the solution. Comments should further the discussion of math and science.

When posting on Brilliant:

  • Use the emojis to react to an explanation, whether you're congratulating a job well done , or just really confused .
  • Ask specific questions about the challenge or the steps in somebody's explanation. Well-posed questions can add a lot to the discussion, but posting "I don't understand!" doesn't help anyone.
  • Try to contribute something new to the discussion, whether it is an extension, generalization or other idea related to the challenge.
  • Stay on topic — we're all here to learn more about math and science, not to hear about your favorite get-rich-quick scheme or current world events.

MarkdownAppears as
*italics* or _italics_ italics
**bold** or __bold__ bold

- bulleted
- list

  • bulleted
  • list

1. numbered
2. list

  1. numbered
  2. list
Note: you must add a full line of space before and after lists for them to show up correctly
paragraph 1

paragraph 2

paragraph 1

paragraph 2

[example link](https://brilliant.org)example link
> This is a quote
This is a quote
    # I indented these lines
    # 4 spaces, and now they show
    # up as a code block.

    print "hello world"
# I indented these lines
# 4 spaces, and now they show
# up as a code block.

print "hello world"
MathAppears as
Remember to wrap math in \( ... \) or \[ ... \] to ensure proper formatting.
2 \times 3 2×3 2 \times 3
2^{34} 234 2^{34}
a_{i-1} ai1 a_{i-1}
\frac{2}{3} 23 \frac{2}{3}
\sqrt{2} 2 \sqrt{2}
\sum_{i=1}^3 i=13 \sum_{i=1}^3
\sin \theta sinθ \sin \theta
\boxed{123} 123 \boxed{123}

Comments

Sort by:

Top Newest

Thanks! I hope you won't mind if I post another link here which contains some basic knowledge on Cryptography (it might help someone out) : Khan Academy Videos on Cryptography.

Kou$htav Chakrabarty - 5 years, 7 months ago

Log in to reply

You re welcome to post any related material:)

Eddie The Head - 5 years, 7 months ago

Log in to reply

Wow, interesting stuff! Who would've imagined how far a supposedly minor theorem such as Fermat's Little Theorem could go?

Cody Johnson - 5 years, 7 months ago

Log in to reply

gr8 stuff ..........

pratyush ranjan Tiwari - 5 years, 7 months ago

Log in to reply

This is amazing! I loved reading this!

Finn Hulse - 5 years, 7 months ago

Log in to reply

Well i always was in need of learnin about this!!.....NOW it;s HERE! thnx "Eddie the Head" i might need to contact u for discussions...if u agree?.see my brilliant profile..

Arya Samanta - 5 years, 6 months ago

Log in to reply

Sure...I'm always available for discussion... also check out my other cryptography posts :)

Eddie The Head - 5 years, 6 months ago

Log in to reply

×

Problem Loading...

Note Loading...

Set Loading...