Homework Help is Here – Start Your Trial Now!
Engineering
Computer Science
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
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
See similar textbooks
icon
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?

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
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
trending now

Trending now

This is a popular solution!

steps

Step by step

Solved in 3 steps

SEE SOLUTIONCheck out a sample Q&A here
Blurred answer
Knowledge Booster
Calculating Power
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.
Similar questions
  • SEE MORE QUESTIONS
Recommended textbooks for you
Database System Concepts
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)
Starting Out with Python (4th Edition)
Computer Science
ISBN:
9780134444321
Author:
Tony Gaddis
Publisher:
PEARSON
Digital Fundamentals (11th Edition)
Digital Fundamentals (11th Edition)
Computer Science
ISBN:
9780132737968
Author:
Thomas L. Floyd
Publisher:
PEARSON
C How to Program (8th Edition)
C How to Program (8th Edition)
Computer Science
ISBN:
9780133976892
Author:
Paul J. Deitel, Harvey Deitel
Publisher:
PEARSON
Database Systems: Design, Implementation, & Manag…
Database Systems: Design, Implementation, & Manag…
Computer Science
ISBN:
9781337627900
Author:
Carlos Coronel, Steven Morris
Publisher:
Cengage Learning
Programmable Logic Controllers
Programmable Logic Controllers
Computer Science
ISBN:
9780073373843
Author:
Frank D. Petruzella
Publisher:
McGraw-Hill Education
SEE MORE TEXTBOOKS