Start 2x speed Bob selects two primes: p = 31 q = 59 Compute: N = p · q = 31 · 59 = 1829 $ = (p - 1) · (q - 1) = 30 · 58 = 1740 Find integer e such that gcd(e, d) = 1 Guess e = 859 and check: gcd(859, 1740) = 1 If the first guess is not relatively prime to p, try another. Using Euclid's algorithm, find A and B such that A · 859+ B. 1740= 1 79. 859 + (-39)1740= 1 79 . 859 = 1 mod 1740 d = 79 is the inverse of 859 mod 1740 Public key: N= 1829 e = 859 Private key: d = 79 Captions A 1. Bob selects two primes p = 31 and q = 59. Bob computes N = p • q = 31 · 59 = 1829 and o = (p – 1) · (q – 1) = 30 · 58 = 1740. 2. Bob guesses a value for e and checks whether gcd(e, $) = 1. Bob repeats the process until he finds an e such that gcd(e, ) = 1. 3. Suppose e = 859. Bob uses Euclid's algorithm to find A and B such that A· 859 + B · 1740 = 1. 4. Since 79 · 859 + (–39) · 1740 = 1, then 79 · 859 = 1 mod 1740. Therefore, d = 79 is %3D the inverse of 859 mod 1740. 5. The public keys are N = 1829 and e = 859. The private key is d = 79.
Start 2x speed Bob selects two primes: p = 31 q = 59 Compute: N = p · q = 31 · 59 = 1829 $ = (p - 1) · (q - 1) = 30 · 58 = 1740 Find integer e such that gcd(e, d) = 1 Guess e = 859 and check: gcd(859, 1740) = 1 If the first guess is not relatively prime to p, try another. Using Euclid's algorithm, find A and B such that A · 859+ B. 1740= 1 79. 859 + (-39)1740= 1 79 . 859 = 1 mod 1740 d = 79 is the inverse of 859 mod 1740 Public key: N= 1829 e = 859 Private key: d = 79 Captions A 1. Bob selects two primes p = 31 and q = 59. Bob computes N = p • q = 31 · 59 = 1829 and o = (p – 1) · (q – 1) = 30 · 58 = 1740. 2. Bob guesses a value for e and checks whether gcd(e, $) = 1. Bob repeats the process until he finds an e such that gcd(e, ) = 1. 3. Suppose e = 859. Bob uses Euclid's algorithm to find A and B such that A· 859 + B · 1740 = 1. 4. Since 79 · 859 + (–39) · 1740 = 1, then 79 · 859 = 1 mod 1740. Therefore, d = 79 is %3D the inverse of 859 mod 1740. 5. The public keys are N = 1829 and e = 859. The private key is d = 79.
Database System Concepts
7th Edition
ISBN:9780078022159
Author:Abraham Silberschatz Professor, Henry F. Korth, S. Sudarshan
Publisher:Abraham Silberschatz Professor, Henry F. Korth, S. Sudarshan
Chapter1: Introduction
Section: Chapter Questions
Problem 1PE
Related questions
Question
I'm having a very difficult time understanding RSA and Euclid's Algo. I understand how to compute N, and I understand how to computer PHI. I get lost when trying to find integer e, such that gcd(e, PHI) = 1 and further. I also do not understand how to find A and B or where "79" and "-39" come from (i.e., 79 * 859 + (-39)1740 = 1).
Can someone please explain this for me in the simplest terms possible?
Transcribed Image Text:PARTICIPATION
8.8.2: Example preparation of public and private keys in RSA.
АCTIVITY
Start
2x speed
Bob selects two primes: p = 31
q = 59
Compute: N = p -q = 31 - 59 = 1829
O = (p - 1) · (q - 1) = 30 · 58 = 1740
Find integer e such that gcd(e, ø) = 1
Guess e = 859 and check: gcd(859, 1740 ) = 1
If the first guess is not relatively prime to ø, try another.
Using Euclid's algorithm, find A and B such that A· 859+ B• 1740= 1
79- 859 + (-39)1740= 1
79 · 859 = 1 mod 1740
d = 79 is the inverse of 859 mod 1740
Public key: N= 1829
e = 859
Private key: d = 79
Captions A
1. Bob selects two primes p = 31 and q = 59. Bob computes N = p·q = 31 · 59 = 1829
and ø = (p – 1) · (q – 1) = 30 · 58 = 1740.
2. Bob guesses a value for e and checks whether gcd(e, ø) = 1. Bob repeats the process until he
finds an e such that gcd(e, ) = 1.
3. Suppose e = 859. Bob uses Euclid's algorithm to find A and B such that
A· 859 + B · 1740 = 1.
4. Since 79 · 859 + (–39) · 1740 = 1, then 79 · 859 = 1 mod 1740. Therefore, d = 79 is
the inverse of 859 mod 1740.
5. The public keys are N = 1829 and e = 859. The private key is d = 79.
%3D
%3D
Expert Solution
This question has been solved!
Explore an expertly crafted, step-by-step solution for a thorough understanding of key concepts.
This is a popular solution!
Trending now
This is a popular solution!
Step by step
Solved in 3 steps
Knowledge Booster
Learn more about
Need a deep-dive on the concept behind this application? Look no further. Learn more about this topic, computer-science and related others by exploring similar questions and additional content below.Recommended textbooks for you
Database System Concepts
Computer Science
ISBN:
9780078022159
Author:
Abraham Silberschatz Professor, Henry F. Korth, S. Sudarshan
Publisher:
McGraw-Hill Education
Starting Out with Python (4th Edition)
Computer Science
ISBN:
9780134444321
Author:
Tony Gaddis
Publisher:
PEARSON
Digital Fundamentals (11th Edition)
Computer Science
ISBN:
9780132737968
Author:
Thomas L. Floyd
Publisher:
PEARSON
Database System Concepts
Computer Science
ISBN:
9780078022159
Author:
Abraham Silberschatz Professor, Henry F. Korth, S. Sudarshan
Publisher:
McGraw-Hill Education
Starting Out with Python (4th Edition)
Computer Science
ISBN:
9780134444321
Author:
Tony Gaddis
Publisher:
PEARSON
Digital Fundamentals (11th Edition)
Computer Science
ISBN:
9780132737968
Author:
Thomas L. Floyd
Publisher:
PEARSON
C How to Program (8th Edition)
Computer Science
ISBN:
9780133976892
Author:
Paul J. Deitel, Harvey Deitel
Publisher:
PEARSON
Database Systems: Design, Implementation, & Manag…
Computer Science
ISBN:
9781337627900
Author:
Carlos Coronel, Steven Morris
Publisher:
Cengage Learning
Programmable Logic Controllers
Computer Science
ISBN:
9780073373843
Author:
Frank D. Petruzella
Publisher:
McGraw-Hill Education