# Understanding public key cryptography example

Frankly, I wasn't sure whether this belongs in crypto.stackexchange.com or here, so forgive me. I've been going through a book where in one of the chapters the author tries to illustrate public key cryptography by imagining a "four-step business plan for Murder Incorporated" in a "world of strong privacy".

1. Arrange for mystery billboards on major highways. Each contains a single long number and the message “write this down.” Display ads with the same message appear in major newspapers.

2. Put a full-page ad in the New York Times, apparently written in gibberish.

3. Arrange a multiple assassination with high-profile targets, such as film stars or major sports figures – perhaps a bomb at the Academy Awards.

4. Send a message to all major media outlets telling them that the number on all of those bulletin boards is a public key. If they use it to decrypt the New York Times ad they will get a description of the assassination, published the day before it happened.

I don't quite understand the mechanics of how the outlets are able to decrypt the ad and get a description of the assassination. Is the ad encrypted with his private key and since both public and the private keys are mathematically related, whatever is encrypted with the private key can be decrypted with the public key (visible on the billboard) and vice versa?

Interesting premise.

Q : "Is the ad encrypted with his private key ..." A : no, I don't believe so

Edit - To clarify, I entertained the possibility that the author meant to say "private key" in item #4, but once you consider the subsequent paragraph in the source (excerpt below), I don't think the ciphertext that describes the crime in advance is encrypted with public-key cryptography. I reckon the author's protagonist is using the same bytes that are in the public key as the key for a symmetric cipher. (In this case, KDF could potentially be HKDF, PBKDF2, Argon2, scrypt, or even a keyed hash-digest.) eg.

broker_pk = PUBLIC_KEY( secret_key )
ciphDetailsOfCrime = E( KDF(broker_pk) , EvilPlanToMakeCelebsEvenMoreFamous )

eph_cli_pk = PUBLIC_KEY( ephemeral_client_secret_key )
kRequestForQuote = DH_or_ECDH( broker_pk , ephemeral_client_secret_key )
ciphRFQ = E( kRequestForQuote , DetailsOfNewTarget )
msg = eph_cli_pk || ciphRFQ


(This is a contrived example that shouldn't be used, especially if conspiring to commit murder and/ or acts of terrorism.) My original answer continues ...

It may be that the author meant to say "private key" in list item #4, however, I suspect the author is thinking about using the public key, posted on billboards, as a symmetric key (or password to be used in some key derivation function - aka. KDF) to decrypt the prior description of the heinously foul act of murdering film celebrities en masse ...

The paragraph that follows is:

"You have now made sure that everyone in the world has, or can get, your public key – and knows that it belongs to an organization willing and able to kill people. Once you have taken steps to tell people how to post messages where you can read them, everyone in the world will know how to send you messages that nobody else can read and how to identify messages that can only have come from you. You are now in business as a middleman selling the services of hit men. Actual assassinations still have to take place in realspace, so being a hit man still has risks. But the problem of locating a hit man – when you are not yourself a regular participant in illegal markets – has been solved."

• @mentallurg I've edited to include details as to how the author might bind a public key (in this case, the bytes in the PK only) to the ciphertext produced with a symmetric cipher. Could you please reconsider your earlier comment and let me know if your criticism still stands, thanks? (ps. I make no suggestion as to the suitability of this scheme: I'm not qualified to determine whether there would be some mathematical interaction that led to the weakening of the security of Murder Incorporated's secret key by re-using its corresponding PK in a symmetric cipher.) – brynk Apr 3 at 4:14
• I appreciate your input. I think the overall theme with his fictional Murder Incorporated is reputation building in the context of public key cryptography. If the author's protagonist is using the same bytes that are in the public key as the key for a symmetric cipher, would that at all undermine his plan to prove that the public key does indeed belong to someone who committed the heinous crime? I'm sorry, my understanding of public key cryptography is very limited. I'm just trying to understand what is supposed to be an example accessible to lay audiences. – bagelstorm Apr 3 at 16:22
• From a maths perspective, I know of no way that using a public key as input into a KDF would undermine the security of its corresponding private key. However, this scheme I proposed is basically security by obscurity, unless the KDF also has some secret component (which would need to be divulged separately). If some crafty individual figured out that the public key was also the symmetric key, then the plot would no doubt be foiled by using cardboard celebrity cutouts instead of the real thing, and Murder Inc's reputation would be in tatters! I'll answer separately with a scheme based on RSA. – brynk Apr 4 at 1:34
• Thanks. Something to think about, though the math here is a little bit beyond me. I think just based off other examples in the book, the answer is likely to be more accessible, but I might be mistaken. In the meantime, I've reached out to the author to see if he's able to weigh in on the issue. – user89438 Apr 10 at 16:46

Q : "Is the ad encrypted with his private key ..." A : indirectly, yes

After some more thought, I can demonstrate a hybrid scheme based on RSA asymmetric cryptography: What is RSA encryption and how does it work? Lake '21. This proposed solution has significant faults, so don't even think about using it! More:

SUMMARY

1. prepare the published ciphers for the newspaper ad and the billboard, ensuring to keep d and n secret:
n = rsa_nums.public_numbers.n  # p*q
e = rsa_nums.public_numbers.e  # 2^16+1
d = rsa_nums.d                 # private key (+n), see https://crypto.stackexchange.com/q/5889

key_for_evil_plan = b'ALLYOURKEYAREBELONGTOUS'
ciphDetailsOfCrime = E( key_for_evil_plan , EvilPlanToMakeCelebsEvenMoreFamous )

key_as_number = int.from_bytes(key_for_evil_plan, byteorder='big')
billboard_ciph = pow(key_as_number, d, n)

1. wait 'til after the initial ruckus dies down a bit, then advertise the public key n and e ...
media_copy_of_key = pow(billboard_ciph, e, n)
key_for_evil_plan = media_copy_of_key.to_bytes( len(key_for_evil_plan), 'big' )
...
from os import urandom as os_urandom
key_RFQ = os_urandom( 32 )
key_rfq_number = int.from_bytes(key_RFQ, byteorder='little')
key_rfq_ciph = pow(key_rfq_number, e, n)
...


WHAT?

Firstly, remember that Python3 exponentiation is pow(base, exp, mod=None).

1. we create a secret key to encrypt the details of our evil plan, key_for_evil_plan, which we will encrypt using RSA
2. generate the encrypted details, ciphDetailsOfCrime, for publishing in the newspaper advert
3. now convert the secret key bytes to a big-endian integer, key_as_number (... it could also be little-endian, so don't start any egg-wars with me! Silverberg, '12) (ps. but only to get the maths to work, not if the padding protocol specifies this!)
4. modular exponentiation to produce the billboard number, billboard_ciph
5. This is what is called RSA Signature Primitive 1 (step 1) in RFC 8017.

Okay, so now we have the first phase of Murder Inc's grandiose plan to big-note itself. Our "hollywood horror" comes off without a hitch, and the world was mortified, so we decide to make Murder Inc's public key available to everybody (by publishing n and e) so they can start throwing work our way, and we can retire .. PHAT OFF THA PROFITS!

When a party holds n and e, they can then recover the key_for_evil_plan and decrypt ciphDetailsOfCrime. Having confirmed that we're the evil genuises that we claim to be, they can now use n and e to send us top-secret requests for quote (RFQs) by running the algorithm in reverse with e, defined as the RSA Encryption Primitive in RFC 8017.

MATHS

From what I can gather, this paper describes the RSA encryption scheme with Optimal Asymmetric Encryption Padding, however, the linked pdf is not hosted on the author's website. (It's not clear to me if this document is still available from rsa.com - I think RFC 8017 would be considered the definitive source.)

So, what are the n, p, q, e and d values? These are the parts of the RSA algorithm that are described in careful detail in Infosec.SE and Crypto.SE discussions, Lake's thorough article, and the RSAES-OAEP paper linked previously. In short, the numbers:

• p and q are very large prime numbers (multiplied to have n reach eg. 3072- or 4096-bit), that conform to various rules that ensure they are not susceptible to known weaknesses
• n is p * q
• e is 2^16+1 (commonly, but may also be other numbers)
• d is derived from e and etn using the Extended Euclidean algorithm
• etn is (p-1)(q-1), used in a test to ensure math.gcd(e,etn) equals 1, which has something to do with Euler's totient function (more: https://stackoverflow.com/q/4647577)
• What rules? At least Safe Primes, 1 == math.gcd(e,n), and 1 == math.gcd(e, etn), ... and probably a lot more if you have a glance at the RSAES-OAEP paper linked in this section.