basic encryption question

[bwanaaa]

in asymmetric encryption, a public key and a private key are portrayed as 2 very large prime numbers. Encryption is described as multiplying your text by one key and decryption is described as multiplying the resultant ciphertext by the other key to get the original message. The obstacle often described to cracking this encryption is the inability of modern hardware to find the factors of a large number that are prime numbers (and potentially an encryption/.decryption key pair) My simple question is that if you already have one of the primes (my public key), then you can use it to decrypt any messages intended for me just by dividing those messages by the public key. So, obviously I am missing the REAL truth.

what is the actual mathematical transform that is asymmetric?

 

[Mark R]

The main function is 'modular exponentiation' i.e. exponentiation modulo n.

If you are unfamiliar with modulo arithmetic, it is sometimes called clockface arithmetic, because it works rather like a clock face. You have a fixed set of numbers, and they 'wrap around' when you go off one end. Eg. if it's 11 o'clock and you want to add 5 hours, you actually calculate 11+5 (mod 12) which is 4. Similarly, 5 * 5 (mod 12) is 1.

Modulo arithmetic is used in a number of key-exchange and public-key asymmetrical algorithms because this 'wrap around' property makes simple numerical behavior become very complex, and difficult to reverse.

The actual encyrption is done using the formula: ciphertext = message ^ pubk2 (mod pubk1)

The decryption can then be done using the formula: message = ciphertext ^ privk (mod pubk1)

See the worked example at wikipedia to see how the components of the keys are derived, and how they interact to encrypt.

 

[bwanaaa]

Tnx muchly. So no it seems that in addition to the private key and the public key, there is also this number, n, involved - which is the product of two prime numbers. However, this number , n, is never mentioned nor alluded to in pki. In fact, nowhere in pgp or gpg or rsa is this third number ever revealed as being necessary to perform encryption/decryption. Yet it appears essential in the example in the wiki. It's not something you can calculate from the keys either.

So one question leads to a riddle and I am still puzzled. I feel like I am conversing with a dweller from the novel, The Algebraist by Banks.

 

[Mark R]

It works as follows:
Choose 2 prime numbers (p and q) and from them calculate n=pq.
Choose another number, e which is not a factor of (p-1)(q-1).
Calculate d, based on (p-1), (q-1) and e.

Both d and e are meaningless on their own - they only work their magic when combined with n. So, they are always distributed together with n. As a result a PGP/GPG 'public key' contains a value of n, and a value for e.

Similarly, a public/private keypair contains values for n, e and d.

Most protocols never mention the actual individual components of the keys and their generators - they just talk of the 'public' and 'private' keys for simplicity.

 

[bwanaaa]

It works as follows:

Most protocols never mention the actual individual components of the keys and their generators - they just talk of the 'public' and 'private' keys for simplicity.

AHA! So there you go, the public key includes n and the real public key. So how does one pull n out of the gobbledy beloved patriot that people put at the end of their published public key? Btw, tnx for taking the time to clarify this. I DID google a lot and kept getting stuck with discrepant descriptions. At times I thought n was part of an older algorithm. Other times I thought n was bundled into the certificate published by 'the certificate authorities'. Never clear it is.

 

[Mark R]

AHA! So there you go, the public key includes n and the real public key. So how does one pull n out of the gobbledy beloved patriot that people put at the end of their published public key?

The PGP file/key/signature format is here.

Note that RSA is not the only method of public key encryption - there are other widely used examples, notably ElGamal (a similar first generation PK algorithm) and Elliptic curve cryptography (a more modern 2nd generation algorithm with a number of advantages).

The precise data that makes up a public key depends on the algorithm. In the case of ElGamal, the private key consists of a random number x, and the public key consists of a description of a "cyclic group" and a number calculated from x using the group.