Plain text attacks without decryption logic

Quora93

5/3/24, 12:08 PM

The CEO of the organization XYZ decides to hold a vote to decide whether employees should be allowed to work from home (WFH) either one, two or three days a week.

All 4 employees of XYZ (excluding the CEO), need to vote either “WFH one”, “WFH two” or “WFH three”. To ensure privacy, the CEO asks employees to send their votes by emailing them to the CEO. Furthermore, the CEO tells them to encrypt their votes using her RSA public key e. The messages are encoded as:

WFH one 7→ 100,
WFH two 7→ 200.
WFH three 7→ 300.

The CEO receives the sequence of ciphertexts:
c1, c2, c3, c4
where ci is the ciphertext from employee i.

For completeness, assume the employees are in the order: Alice, Bob, Charlie, Dave So, e.g., Bob’s ciphertext is c2.

Was easy:
Assume you, the eavesdropper, gets the sequence: 208149, 249575, 272202, 249575 After observing this, how many possible sequences of votes are there and why? Answer: No. of possible sequences can be calculated as follows: 3 (options for Alice) × 1 (same option for Bob and Dave) × 3 (options for Charlie) = 3 × 1 × 3 = 9
Is bit tricky:
Suppose the CEO’s RSA public key is (N, e) = (311119, 11). What is Charlie’s vote? How did you come to this conclusion? Your answer should not involve any decryption.

I tried the good old $c ≡ m^e (mod N)$ logic, but it didn't work as expected :(

0 + 9

Eugene Styer

5/3/24, 2:08 PM

Hint: What happens when you encrypt the message 2m?

Eugene Styer

5/3/24, 5:00 PM

Alternate idea: The process of encrypting m works for me, is there a problem in your logic?

fgrieu

5/3/24, 7:50 PM

The question's proposed answer for 1 is wrong. Hint: in 1, assume you know neither N nor e, and it's used textbook RSA, which is a bijection. You notice that the the first three intercepted values are distinct, what can you conclude of the votes of Alice, Bob, Charlie? You notice that the second and fourth intercepted values are identical, what can you conclude of the votes of Bob and Dave? Now, how many possible votes for Alice? And then for Bob and Dave? And then for Charlie? For 2: just compute $m^e\bmod N$ correctly and conclude.

fgrieu

5/3/24, 7:53 PM

@Eugene Styer: your hint "What happens when you encrypt the message 2m?" is of no help in 1, and of little to no help in 2.

Quora93

5/4/24, 8:07 AM

@fgrieu by your logic for 1st one: Alice: Since Alice's vote is distinct from Bob's and Charlie's, she can have only one possible vote. Bob and Dave: They have the same vote, but it could be any of the three options, so there are three possible votes for Bob and Dave. Charlie: Charlie's vote is distinct from both Alice's and Bob's, so he can have only one possible vote. By considering these possibilities, we can conclude that there are 1 (Alice) * 3 (Bob and Dave) * 1 (Charlie) = 3 possible sequences of votes.

Quora93

5/4/24, 8:08 AM

@fgrieu yes I had miscalculated, the good old formulae works fine.

fgrieu

5/4/24, 9:00 AM

I'm counting three possibilities for Alice, then _for each such possibilities_ two remaining possibilities for Bob and Dave, and then one remaining possibility for Carol; thus 3×2 possibilities for the sequence of votes: 1232, 1323, 2131, 2313, 3121, 3212. But then I may have misunderstood what's asked.

Quora93

5/5/24, 4:36 AM

Hi @fgrieu Then actually 9 possible sequences of votes based on the intercepted ciphertexts. Here is the list of all the possibilities: Alice: 1, Bob: 2, Charlie: 3, Dave: 2// Alice: 1, Bob: 3, Charlie: 2, Dave: 2// Alice: 1, Bob: 2, Charlie: 2, Dave: 3// Alice: 2, Bob: 1, Charlie: 3, Dave: 2// Alice: 2, Bob: 3, Charlie: 1, Dave: 2// Alice: 2, Bob: 1, Charlie: 2, Dave: 3// Alice: 3, Bob: 1, Charlie: 2, Dave: 2// Alice: 3, Bob: 2, Charlie: 1, Dave: 2// Alice: 3, Bob: 2, Charlie: 2, Dave: 1//

fgrieu

5/5/24, 7:28 AM

I disagree. Your sequence "Alice: 1, Bob: 3, Charlie: 2, Dave: 2" can't be, because we know that Bob and Dave voted the same (something that enciphers to 249575), and also because we know Charlie and Dave voted differently (since the vote of Charlie enciphers to 272202 and the vote of Dave enciphers to the different 249575). Among the 9 sequences that you list, only " Alice: 1, Bob: 2, Charlie: 3, Dave: 2" and " Alice: 3, Bob: 2, Charlie: 1, Dave: 2" are among the 6 possible sequences given the observation made.

Elon Musk

I sit in a Tesla and translated this thread with Ai:

EN: Plain text attacks without decryption logic

Post an answer

Most people don’t grasp that asking a lot of questions unlocks learning and improves interpersonal bonding. In Alison’s studies, for example, though people could accurately recall how many questions had been asked in their conversations, they didn’t intuit the link between questions and liking. Across four studies, in which participants were engaged in conversations themselves or read transcripts of others’ conversations, people tended not to realize that question asking would influence—or had influenced—the level of amity between the conversationalists.