5
$\begingroup$

I am working on assignment where I have specific scenarios and I am little bit struggling with this one.

Alice sends and email to Bob.For this e-mail, she uses the following method of encryption: each single word of the text is viewed as an integer number in binary, obtained by concatenating the 8-bit binary values of the ASCII code of each letter. The number thus obtained for each word is then encrypted using the RSA algorithm and the resulting list of numbers is sent. Words that are too long to fit into this scheme are split into syllables, and each syllable is treated as a word.

I need to discuss whether eve can find efficient method to decrypt messages. My answer is:

I know if the plain text has two or more blocks of plaintext in common then we get same result for each of these blocks. This is the bit of information that leaks even if this does not give immediate information what the original plain text might be, Eve can see the relationship between plaintext and cipher text.

Eve can also measure how much power /time it takes to decrypt cipher text. Eve can observe this power and time consumption and she might be able to get some information about how many “1” there are in d. If Eve manages to determine d she can decrypt entire cipher text as c^d mod n =m.

I also need to provide rough estimation about the time it would take to decrypt the message and this is the part I am struggling with. The estimates of the time could be of the type: a few seconds, a few minutes, 1 hour, a few hours, one day, one week or longer. You may make assumptions about the speed of her computer: for example you could assume it would take 1 millisecond to perform RSA to encrypt or to decrypt one integer (of any size commonly used in RSA), if the encryption, respectively decryption key is given.

Any suggestions?

Improve this question
$\endgroup$
1
  • 6
    $\begingroup$ Hint1: if Alice does not use random padding, Eve (knowing the public key) can encipher each word in the dictionary just as Alice does. Hint2: that words may have to be split suggests that an unsafe modulus is used. $\endgroup$
    – fgrieu ♦
    Commented Nov 19, 2015 at 19:15

1 Answer 1

Reset to default
2
$\begingroup$

This is basically a substitution cipher where words are converted to numbers and then those numbers are substituted for new numbers as the encryption step. You'd need to assume the language of plaintext, let's assume it's English.

Every time the word "the" occurs in the original text, it will cause the same number to be output to replace it. Using some word frequency tables, it may be possible to find patterns that occur in the cyphertext that represent common patterns in English usage.

I guess I would have to look and see if there is a technical definition for decrypt, but even if you managed to puzzle out a possible sentence by analyzing the cyphertext, does that count as a decryption if you cannot reproduce your assumed input generating the same output.

Despite this being a very bad way to use RSA, it would still not make it any easier to officially decrypt the message. The only way to do this with absolute certainty, is to factor the primes that make up the private key. Depending on the size of the primes involved, this is a pretty intractable problem...

As the commentor above notes... if a word won't fit into the modulus, then keysize might be pretty small. The longest word in English is something like 28 letters, so 28*8 is 224 bits. There is no way that antidisestablishmentarianism was what the question had in mind, so lets make an assumption that any word longer than 8 characters is one that would need to be broken up... That would be a modulus of 64 bits. So now, the question is, how long would it take to factor a 64 bit number. On modern computers, one assumes that could be handled in minutes. ( https://stackoverflow.com/questions/4244319/how-to-find-all-the-prime-factors-in-a-unsigned-long-long-integer )

Improve this answer
$\endgroup$
8
  • 1
    $\begingroup$ Unpadded RSA also means you can verify your correct guesses when you know the public key, so it should count as "official". (If it is padded, frequency analysis is not necessarily possible either.) $\endgroup$
    – otus
    Commented Nov 20, 2015 at 10:22
  • $\begingroup$ Even better :if the public key is known, and there is no random padding, you need only to guess what words are used; their position is then found without guess. Without random padding and if the public key is not initially known, we need to successfully guess some words (perhaps based on frequency analysis), then determine the public key. If random padding is used, the analogy with substitution cipher breaks down entirely. $\endgroup$
    – fgrieu ♦
    Commented Nov 20, 2015 at 10:30
  • $\begingroup$ I don't believe, it being asymmetric encryption that you can go backwards from cyphertext to plaintext using the public key. You would just get a new encryption of the cyphertext that only the private key could decrypt back into the original cyphertext. $\endgroup$
    – P Holder
    Commented Nov 20, 2015 at 10:39
  • $\begingroup$ @PHolder, the point is that if you encrypt the word "the" deterministically, it is always the same ciphertext. With RSA you can encrypt any test word you like using just the public key. So if you find one word matches the ciphertext you know for "the", you know the plaintext. $\endgroup$
    – otus
    Commented Nov 20, 2015 at 10:49
  • 1
    $\begingroup$ @PHolder, yes I have. I can do Encrypt(public_key, "the") and compare that to the ciphertext. There is only one possible word that could have been encrypted to that ciphertext, or else the encryption is not decryptable in the first place. $\endgroup$
    – otus
    Commented Nov 20, 2015 at 10:54

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.