Search Results for: DiqLullh6CBE

RSA Public Key Private Key Encryption – Table of Contents TOC

• RSA Public Key Private Key Encryption – Table of Contents TOC
• Search Page: DiqLullh6CBE
• ——————————————————————————–
• Shor Algorithm by the Numbers
• RSA is mathematically symmetric in e and d
• RSA Public Key Private Key Encryption – A Practical Example

The RSA setup You start by picking two large secret primes p and q, then compute: N = p · q — the modulus. In the article's example, p = 7, q = 11, so N = 77. N is public. φ(N) = (p − 1)(q − 1) — Euler's totient of N. Size of the multiplicative group mod N, and it's secret. For N = 77, φ(77) = 6 · 10 = 60. e — the public encryption exponent. You pick any e with 1 < e < φ(N) and gcd(e, φ(N)) = 1. Common choice is e = 65537. e is public. d — the private decryption exponent. It's the modular inverse of e mod φ(N), i.e. the unique d with e · d ≡ 1 (mod φ(N)). d is secret. The keys Public key = (N, e) — you publish this. Anyone can encrypt a message m by computing c = m? mod N. Private key = (N, d) — you keep this. You decrypt with m = c? mod N. It works because of Euler's theorem: m^(ed) ≡ m^(1 + kφ(N)) ≡ m (mod N). p and q are the secret primes you use to derive d. If an attacker learns p and q, they can compute φ(N) and then d, so factoring N breaks RSA. That's exactly why Shor's algorithm matters: it factors N efficiently on a quantum computer, which hands the attacker φ(N), then d, then the private key.

RSA is mathematically symmetric in e and d, so swapping keys still gives valid encryption and decryption. But in practice this is a bad idea, and understanding why is more interesting than the math itself.

Why it works mathematically

RSA's correctness comes from Euler's theorem: for any m coprime to N,

because

ed ≡ 1 (mod φ(N)).

This equation is completely symmetric in e and d — the math doesn't care which one you call "public" and which "private." If you defined "encrypt" as c = m^d mod N and "decrypt" as m = c^e mod N, the round trip still works.

So if Alice publishes d and keeps e secret, Bob can encrypt with d and Alice can decrypt with e. The algebra is identical.

In fact, this symmetry is exactly what powers RSA signatures: to sign a message, Alice computes s = m^d mod N with her private key, and anyone can verify with s^e mod N = m using her public key. Signing is "encrypting with the private key" — the same operation, just conceptually reversed.

Why you shouldn't actually swap them

Three practical reasons the roles are not interchangeable in a deployed system:

1. e is chosen small on purpose.
Real RSA uses

almost universally. It has only two 1-bits in binary, so m? mod N takes about 17 modular multiplications — encryption and signature verification are very fast. d, by contrast, is a full-size number roughly log?(N) bits long (2048 or 4096 bits in modern use). If you swap them, every "encryption" now costs thousands of modular multiplications instead of 17. Verification of signatures becomes as expensive as signing. You'd throw away a large constant-factor performance win for no benefit.

2. Small e is only safe as the public exponent.
A small e is secure because d, computed as ends up being large and unpredictable. If you instead publish d and keep e = 65537 secret, then "secret e" isn't secret at all — an attacker just guesses 65537 (or tries the handful of common small e values) and decrypts everything. The whole security assumption relies on the private exponent being large. Small-private-exponent RSA is catastrophically broken; there's a famous result by Wiener showing that if the private exponent is smaller than roughly N^(1/4), you can recover it in polynomial time from the public key.

3. Standards, key formats, and libraries assume the conventional roles.
PKCS#1, X.509 certificates, TLS, SSH, OpenPGP, and every cryptographic library encode "e is public, d is private" into their data structures and APIs. A key file literally has fields named publicExponent and privateExponent. Swapping them would break interoperability with everything.

Summary

• Mathematically: e and d are interchangeable
• Cryptographically: they are not interchangeable, because the security proof requires the private exponent to be large and unpredictable, and the public exponent is deliberately chosen small for speed.

The symmetry is real and useful (it's what makes signatures work), but "swap them and use the system backwards" would give you a functioning but slow and insecure cryptosystem.

Numeric Example of the Shor Algorithm

See Chapter 10 of the book: Algorithms  for greater detail.

LibreOffice SpreadSheet with these same calculations:  Shor-Algorithm-By-The-Numbers-Amarketplaceofideas-com.ods

The RSA setup You start by picking two large secret primes p and q, then compute: N = p · q — the modulus. In the article's example, p = 7, q = 11, so N = 77. N is public. φ(N) = (p − 1)(q − 1) — Euler's totient of N. Size of the multiplicative group mod N, and it's secret. For N = 77, φ(77) = 6 · 10 = 60. e — the public encryption exponent. You pick any e with 1 < e < φ(N) and gcd(e, φ(N)) = 1. Common choice is e = 65537. e is public. d — the private decryption exponent. It's the modular inverse of e mod φ(N), i.e. the unique d with e · d ≡ 1 (mod φ(N)). d is secret. The keys Public key = (N, e) — you publish this. Anyone can encrypt a message m by computing c = m? mod N. Private key = (N, d) — you keep this. You decrypt with m = c? mod N. It works because of Euler's theorem: m^(ed) ≡ m^(1 + kφ(N)) ≡ m (mod N). p and q are the secret primes you use to derive d. If an attacker learns p and q, they can compute φ(N) and then d, so factoring N breaks RSA. That's exactly why Shor's algorithm matters: it factors N efficiently on a quantum computer, which hands the attacker φ(N), then d, then the private key.

 

   

Factoring the product is a difficult computation task in the case of large prime numbers.  In this case it is obvious for the example's purposes

 

Factor 77 using Shor's algorithm

Pick a number that is relative prime to both 7 and 11.   Here we choose  5 for the example.  

 will be periodic in r.   The following would be set up in a quantum register to have all the values in the register simultaneously and calculate the function results simultaneously.

•   
•  
•  
•  
• 
•  
•  
•   
•  
•  
• 
•  
•  
•  
•  
• 
•  
•  
•   
•  
•  
• 
•  
•  
•  
•  
• 
•  
• 
•     Starts repeating here
•     Calculate one more to check up above to convince yourself the exponential function is indeed periodic

Here we see the form of even power of the variable with 1 left over after the mod. That allows transforming the equation to the easily factored form of an  even power minus one that can be factored.    The even power is not guaranteed to you keep trying solutions till you get an even periodicity.

  

  

After the above results are piled simultaneously in the quantum register a quantum FFT is performed and the period r found to be 30 with high probability.     All the above mod result values are in the register at the same time and not indexed per time or pure number index as far as I know.  A quantum FFT does not yield a spectrum.  It yields a frequency estimate of highest probability of the input waveform.   Frequency as in probability frequency.  However the above mod result values are KNOWN to be in regular spacing so a frequency that we are accustomed to can be calculated.

Thus using

       have common factors with 77.  

     

Calculators

• greatest common factor calculator webpage 
• Integer factorization calculator

Each of 77's 2 coprime factors have a common factor with only  one of the 2 terms above.  *(Not sure yet how to prove that)  Use Euclid's rule to find the greatest common divisor

Perplexity: Since N | (a^r – 1) = (a^(r/2) – 1)(a^(r/2) + 1) and N ? either factor alone (because r is the smallest period), each prime factor of N must divide one of the two terms. It is also possible for both primes to divide the same term (in which case the algorithm fails and you retry with a new a); the guarantee is only probabilistic. The page's phrasing that each factor hits only one of the two terms is not generally true it happens to be true here.   

Greatest Common Divisor.  See chapter 1.2.3 of Algorithms.\

• 
• 
•      30517578124 = 2² × 11 × 31 × 71 × 181 × 1741
•      30517578126 = 2 × 3² × 7 × 61 × 521 × 7621

 

With this being the Kpub and Kpriv  ( public and private key ) 

 

and the problem is solved.