### Re: Raw RSA binary string and public key 'detection'

* Dirk-Willem van Gulik: Been looking at the Telnic (dev.telnic.org) effort. In essence; NAPTR dns records which contain private details such as a phone number. These are encrypted against the public keys of your friends (so if you have 20 friends and 3 phone numbers visible to all friends - you need 20 subdomains x 3 NAPTR entries under your master'). Aside from the practicality of this - given a raw RSA encrypted block and a list of public keys - is there any risk that someone could establish which of those public keys may have been used to create that block ? If the padding scheme is decent, this should not be possible without breaking RSA. However, the proposal limits keys to about 250*6 bits, which seems rather restrictive for RSA keys. I'm also concerned about reflective attacks were you ask someone who's trusted by the data owner to decrypt the data for you, possibly in an automated fashion. - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]

### Raw RSA binary string and public key 'detection'

Been looking at the Telnic (dev.telnic.org) effort. In essence; NAPTR dns records which contain private details such as a phone number. These are encrypted against the public keys of your friends (so if you have 20 friends and 3 phone numbers visible to all friends - you need 20 subdomains x 3 NAPTR entries under your 'master'). Aside from the practicality of this - given a raw RSA encrypted block and a list of public keys - is there any risk that someone could establish which of those public keys may have been used to create that block ? I.e. something which would be done in bulk for large populations; so the use of large tables and what not is quite warranted. Thanks, Dw - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]

### Re: Raw RSA

On Sun, 10 Sep 2006, James A. Donald wrote: Could you describe this attack in more detail. I do not see a scenario where it would be useful. Suppose that an attacker runs an activex control on the user's computer and the control is able to ask a smart card connected to the computer to perform raw RSA operations with user's private key. The goal of the attacker is to be able to sign some useful messages with the user's private key *after* the user disconnect his smart card. The attacker can encrypt a subset of numbers - those that encrypt to a B smooth number, but for this to be useful to him, he has to find a number in the subset set that corresponds to what he desires to encrypt, which looks like a very long brute force search. If the attacker needs to sign a message x, he needs to find a smooth number y = x + k n, where n is the RSA modulus and k is some arbitrary number. I forgot what was the algorithm to find such y (I am not even sure that it exists), IIRC, it was based on LLL. -- Regards, ASK - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]

### Re: Raw RSA

Leichter, Jerry wrote: | It is known, that given such an oracle, the attacker can ask for | decryption of all primes less than B, and then he will be able to | sign PKCS-1 encoded messages if the representative number is B-smooth, | but is there any way to actually recover d itself? RSA is multiplicative, so, yes, this follows easily unless the encoding used prevents it. Could you describe this attack in more detail. I do not see a scenario where it would be useful. The attacker can encrypt a subset of numbers - those that encrypt to a B smooth number, but for this to be useful to him, he has to find a number in the subset set that corresponds to what he desires to encrypt, which looks like a very long brute force search. - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]

### Re: Raw RSA

I don't follow. For RSA, the only difference between encryption and decryption, and public and private key, and hence between chosen plaintext and chosen ciphertext, is the arbitrary naming of one of a pair of mutually-inverse values as the private key and the other as the public key. -- Jerry Negative, Jerry. There is a very big difference between which one you make public and which one you make private. The difference is that the public one is given out to the world. It is well known that if d (the RSA private exponent) is small enough, it can be recovered via Wiener's continued fraction attack or the several extensions of it. I think Wiener's attack worked if d N^{1/4}, and Boneh (with Glenn Durfee) brought this up to N^{.292}. There is a conjecture that d needs to be sqrt(N), but no one's come close to proving this. So it IS important which one you name as the private key: name the bigger one! :) john// - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]

### Re: Raw RSA

| | It is known, that given such an oracle, the attacker can ask for | | decryption of all primes less than B, and then he will be able to | | sign PKCS-1 encoded messages if the representative number is B-smooth, | | but is there any way to actually recover d itself? | | RSA is multiplicative, so, yes, this follows easily unless the encoding | used prevents it. | | Could you describe this attack in more detail. I do not see a scenario where | it would be useful. | | The attacker can encrypt a subset of numbers - those that encrypt to a B | smooth number, but for this to be useful to him, he has to find a number in | the subset set that corresponds to what he desires to encrypt, which looks | like a very long brute force search. Let R(x) = x^k mod n - where k might be the public key - for encryption - or the private key - for signing. R(xy) = R(x)R(y) mod n. For encryption, this means little - since the encryption exponent is public, anyone can compute R(xy) directly anyway. But for signing, it means that if I have my hands on signed copies of x and y, I can forge a signature on xy. Thus, if I am able to get signatures on a good collection of primes, I can sign many messages easily. Yet another reason to sign hashes of messages, not raw messages - and that the signer module should compute the hash itself, not rely on the caller to do it. -- Jerry - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]

### Re: Raw RSA

| Hi. | | If an attacker is given access to a raw RSA decryption oracle (the | oracle calculates c^d mod n for any c) is it possible to extract the | key (d)? If I hand you my public key, I have in effect handed you an oracle that will compute c^d mod n for any c. What you are asking is whether you can then extract my private key e - which is exactly what the security claims for RSA say you cannot do. (Note that I chose to call my public key d and by private key e - but since the two keys are completely equivalent in RSA, that's just naming.) | It is known, that given such an oracle, the attacker can ask for | decryption of all primes less than B, and then he will be able to | sign PKCS-1 encoded messages if the representative number is B-smooth, | but is there any way to actually recover d itself? RSA is multiplicative, so, yes, this follows easily unless the encoding used prevents it. -- Jerry | -- | Regards, | ASK | | - | The Cryptography Mailing List | Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED] | - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]

### Re: Raw RSA

On Thu, 7 Sep 2006, Leichter, Jerry wrote: | If an attacker is given access to a raw RSA decryption oracle (the | oracle calculates c^d mod n for any c) is it possible to extract the | key (d)? If I hand you my public key, I have in effect handed you an oracle that will compute c^d mod n for any c. What you are asking is whether you can then extract my private key e - which is exactly what the security claims for RSA say you cannot do. (Note that I chose to call my public key d and by private key e - but since the two keys are completely equivalent in RSA, that's just naming.) I want to extract the exponent that is used by the oracle: this is the difference between the chosen-plaintext attack (it does not require an oracle, since it is a public key scheme) and the chosen-ciphertext attack (CCA1). -- Regards, ASK - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]

### Re: Raw RSA

Alexander Klimov asks: If an attacker is given access to a raw RSA decryption oracle (the oracle calculates c^d mod n for any c) is it possible to extract the key (d)? This is equivalent to asking whether factoring reduces to RSA inversion. That is, given access to an RSA inversion oracle, can you factor the modulus? (Factoring the modulus is equivalent to finding d.) Then see Breaking RSA May Not Be Equivalent to Factoring by Boneh and Venkatesan, Eurocrypt 98. Abstract (with my added emphasis): We provide evidence that breaking low-exponent RSA cannot be equivalent to factoring integers. We show that an algebraic reduction from factoring to breaking low-exponent RSA can be converted into an efficient factoring algorithm. THUS, IN EFFECT AN ORACLE FOR BREAKING RSA DOES NOT HELP In FACTORING INTEGERS. Our result suggests an explanation for the lack of progress in proving that breaking RSA is equivalent to factoring. We emphasize that our results do not expose any specific weakness in the RSA System. So the answer would appear to be no, an oracle for RSA does not help in factoring and therefore will not reveal d. See also http://citeseer.ist.psu.edu/bellare01onemorersainversion.html The One-More-RSA-Inversion Problems and the Security of Chaum's Blind Signature Scheme by Bellare et al for some discussion of this issue. Hal Finney - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]

### Re: Raw RSA

| | If an attacker is given access to a raw RSA decryption oracle (the | | oracle calculates c^d mod n for any c) is it possible to extract the | | key (d)? | If I hand you my public key, I have in effect handed you an oracle that | will compute c^d mod n for any c. What you are asking is whether you | can then extract my private key e - which is exactly what the security | claims for RSA say you cannot do. (Note that I chose to call my | public key d and by private key e - but since the two keys are | completely equivalent in RSA, that's just naming.) | | I want to extract the exponent that is used by the oracle: this is the | difference between the chosen-plaintext attack (it does not require an | oracle, since it is a public key scheme) and the chosen-ciphertext | attack (CCA1). I don't follow. For RSA, the only difference between encryption and decryption, and public and private key, and hence between chosen plaintext and chosen ciphertext, is the arbitrary naming of one of a pair of mutually-inverse values as the private key and the other as the public key. -- Jerry | -- | Regards, | ASK | | - | The Cryptography Mailing List | Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED] | - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]

### Raw RSA

Hi. If an attacker is given access to a raw RSA decryption oracle (the oracle calculates c^d mod n for any c) is it possible to extract the key (d)? It is known, that given such an oracle, the attacker can ask for decryption of all primes less than B, and then he will be able to sign PKCS-1 encoded messages if the representative number is B-smooth, but is there any way to actually recover d itself? -- Regards, ASK - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]