Gate 2017
Duration: 4 min
This video lesson is available to enrolled students.
AI Summary
An AI-generated summary of this video lecture.
The video provides a tutorial on solving an RSA cryptosystem problem from the GATE 2017 exam. The instructor presents the problem where user A uses primes p=13 and q=17, with public key e=35, asking for private key d. He outlines the six-step RSA algorithm, emphasizing n, phi(n), and e selection. The lecture focuses on deriving d using the modular multiplicative inverse formula. The instructor demonstrates the trial-and-error method for finding integer k in d = (1 + k * phi(n)) / e, calculating the correct private key value. This is a standard problem type for cryptography exams. The video helps students understand the mathematical foundations of public-key cryptography.
Chapters
0:00 – 2:00 00:00-02:00
The instructor introduces the problem: "In a RSA cryptosystem a particular A uses two prime numbers p = 13 and q = 17... If the public key of A is 35." He lists six standard RSA steps, highlighting step 2 "Calculate n = p * q" and step 3 "Calculate phi(n) = (p-1) * (q-1)". He identifies p=13, q=17, e=35. He calculates n = 13 * 17 and phi(n) = 12 * 16 = 192. He circles step 5: "Calculate d, such that d * e = 1 mod phi(n)". He emphasizes 'e' must be coprime to phi(n) and gcd(e, phi(n)) = 1. He also notes that 1 < e < phi(n). The slide clearly shows the steps 1 through 6.
2:00 – 3:51 02:00-03:51
The instructor writes d * e = 1 mod phi(n). He rearranges it: d = (1 + k * phi(n)) / e. He substitutes values: d = (1 + k * 192) / 35. He tests k values. For k=0, d=1/35. For k=1, d=193/35. For k=2, numerator is 1 + 384 = 385. He divides 385 by 35 to get 11. He circles "11". He shows a calculator app to verify. This substitution is key to solving modular inverse problems manually. The visual calculation helps clarify the process. He explicitly writes k=0, 1, 2, 3. The calculator shows the division result.
The lesson bridges theoretical RSA steps with practical calculation. By breaking down finding n, phi(n), and solving the modular inverse equation, the instructor demonstrates a clear method for finding the private key. The trial-and-error method for k is practical for small numbers in exams. This ensures students understand the computational process for modular multiplicative inverse. Visual aids reinforce learning. The step-by-step approach is crucial for exam preparation. The video covers the entire process from problem statement to final answer. It is a valuable resource for GATE aspirants.