# Tag Info

2

Doesn't this reduce the search space for the primes P and Q by half? I can't see how it does. After all the attacker can see $N$, and so can determine what bits are set. Allowing, say, a 2047 bit composite (rather than a 2048 bit) doesn't make his job any harder; he can see whether the composite in front of him is either 2047 or 2048 bits long. What ...

10

This is a common mistake, so I'd like to give an in-depth answer. Basically, what you are proposing is to rely on the ONE-WAYNESS of RSA as a ONE-WAY FUNCTION, rather than relying on its CPA or CCA security as an encryption scheme. The advantage of using RSA as a one-way function is that no padding etc is needed. Now, the first important thing to note is ...

5

Choosing $\lambda(n)$ rather than $\varphi(n)$ may result in a smaller private exponent.

3

It should be proven in any presentation of RSA that, with a correct public modulus $N$, public exponent $e$ and private exponent $d$, all integers $m \in \{0,1,\dots,N-1\}$ satisfy $$\left(m^e\bmod N\right)^d\bmod N = m.$$ So it is only possible for a number to "not encrypt or decrypt correctly" when it is not in $\{0,1,\dots,N-1\}$. Moreover, this necessary ...

1

Making sure this oracle you're talking about is not available to an attacker is a bit harder than just saying so. When we first heard of the Vaudenay attack on CBC (https://www.iacr.org/archive/eurocrypt2002/23320530/cbc02_e02d.pdf) we thought that we had done enough to "get rid of the oracle" and we found out with the Lucky13 attack ...

0

The problem with DRM is that the keys must be revealed to the end user machine and thus susceptible to interception. Not to mention I believe that the Sony PlayStation uses ECDSA to secure its firmware and it got cracked.

4

Your description of the protocol is rather confused. You seem to jump between a key and an encryption output. It isn't clear whether you're worried about the key generation process, or an encryption operation that happens with this key. I assume that you're talking about RSA with a 128-byte key, not 128-bit — 128 bits was already insecure when RSA was ...

1

In RSA, $\phi(N)$ is hidden and this is why nobody could calculate private key. For a prime modulus, order of multiplicative group is not a secret. Well, this question looks like encouraging your own thinking of RSA and related arithmetic, so please keep digging in.

2

So let's first recall how blinded RSA works: Select primes $p=11$ and $q=29$, calculate the modulus $n=pq=209$, choose a public exponent $e=7$. Now calculate the signature exponent $d\equiv e^{-1} \pmod{(p-1)(q-1)}$ ($d=103, (p-1)(q-1)=180$). Now let's go to the message-dependant processing: A message $M$ is represented as the integer $m$ which is blinded ...

5

PKCS#1 padding succeeds in introducing enough entropy (slightly less than 64 bits at the very minimum) to make RSA encryption semantically secure. Furthermore, the number $m$ - the message used for modular exponentiation - it produces will be large enough to protect against attacks that rely on $m$ to be small. That means that the premisses for RSA modular ...

0

As for the algorithm, you have two choices: The quadratic sieve and the general number field sieve. If you want to implement the factorization yourself you want to use the quadratic sieve, as a good implementation of the GNFS is really hard. However, if you're willing to use pre-made tools using GGNFS and msieve (together) is your best option. Msieve ...

0

If the moduli share no commonness / weak properties, it's impossible to solve the problem as given at hand. (As CodesInChaos pointed out) Now as you're given RSA moduli, which are always constructed as $n=pq$, you can be sure that if you find $gcd(n_1,n_2)=R>1$, than either $R=p$ or $R=q$ must hold. As you pointed out in the comments you indeed found ...

2

"RSA/ECB/PKCS1Padding" - as you already found out - is not really implementing ECB. For instance Bouncy Castle also has "RSA/None/PKCS1Padding" to mean the same thing. ECB is used for block cipher modes of operation, and RSA is not a block cipher. For block ciphers ECB makes some kind of sense; it basically means performing the block cipher operation for ...

1

It's not the algorithm that's more "efficient" (that's just a welcome side-effect) but the security level. Security levels are usually given in bits; to say that a cipher has 80 bits of security means that we assume it takes roughly $2^{80}$ effort to break it, for some definitions of "effort" and "break". For RSA, the main problem is factoring large ...

2

As far as the standard (PKCS#1) is concerned, the primes need not have the same length; the smallest should not be "too small" to avoid getting in range of the ECM factorization method, but there is still a lot of margin here. However, some implementations can be more limited. For instance, Windows' implementation of RSA (in CryptoAPI) assumes that, for a ...

4

The original poster clarified that: the application of RSA is signature (not encryption as originally stated); at least one signature $s$, the value of $N$, and $e=3$ are given; the signature is by signing an MD5 hash of a message, and a hash of the message matching the signature $s$ is also a given. The first, low-effort thing to do with the givens is ...

3

There are three main errors here: Exponent $e$ must be chosen to be coprime with $\phi$. In your question, exponent $e = 3$ is not coprime with $\phi = 1008$. You can choose $e = 5$ instead. You must use integer arithmetic, not floating-point. In other words, you cannot have values expressed with decimals. You cannot encrypt a message bigger than the ...

0

This is basically the difference between e.g. the RSA_ ciphersuites and the DHE_/ECDHE_ ciphersuites in the TLS protocols. Currently the standardization moves towards ECDHE_ because it provides forward secrecy: even if you factor the RSA key you can still not decrypt previous transmissions. Note that you don't have to MAC the session key before encryption ...

0

I implemented this padding oracle attack some time ago in Python and remember this part being a bit confusing to wrap my head around, my code is as follows: newM = [] for (a, b) in M: # util.ceiling rounds arg1 / arg2 to the next highest integer rlow = util.ceiling((a*s - 3*B + 1), n) rhigh = (b*s - 2*B) / n for r in range(rlow, rhigh + 1): ...

2

1

If you can recover the private key from a message and a signature (and the public key), then that signature method is broken, and broken quite bad. We believe that RSA, with a decent signature padding method, is secure, and hence the specific failure mode you mentioned cannot happen. There are two obvious ways to try to recover the private key for RSA; we ...

0

Please refer the document at NIST site pointing to the document (800-22-rev 1a ) updated on April 2010 (http://csrc.nist.gov/publications/nistpubs/800-22-rev1a/SP800-22rev1a.pdf). The list of special published (SP) documents are available at (http://csrc.nist.gov/publications/PubsSPs.html) It involves some reading, but should get your answers. Since it ...

2

On encrypting the same plain text, I get two different outputs. This is in fact a design goal of encryption systems: an adversary who sees two ciphertexts should not be able to tell whether they're equal — that would be an information leak. Even encryption systems that would otherwise be secure use an initialization vector or other similar unique value ...

2

Am I correct in assuming the above? No you are not. You are showing textbook/raw RSA, which is little more than modular exponentiation. To be secure RSA has to use padding methods. Without padding, RSA would indeed generate the same ciphertext each time. This alone would break the security requirements of a cipher. There are many other attacks on ...

2

Yes, in your specific case, $d=1031$ is the answer. You can check it in the following ways: Just try it out. Select some arbitrary messages, exponentiate with $e$, apply the modulus and exponentiate them with $d$. If this yields your original message number (like 20 or 5001) you know it's the correct $d$. Factor $N$ using the exponent. You may want to use ...

1

At first I want to cite Lindell and Katz book: A "plain Rabin" encryption scheme, constructed in a manner analogous to plain RSA encryption, is vulnerable to a chosen-ciphertext attack that enables an adversary to learn the entire private key. Although plain RSA is not CCA-secure either, known chosen-ciphertext attacks on plain RSA are less damaging ...

0

What does an RSA signature look like? I found this in P1363 Public Key Cryptography. Its an older copy of the standard from 2000. It may (or may not) be current. On page 41, there is 8.2.6 IFSP-RSA2, which stands for Integer Factorization, Signing Primitive. RSA2 is the second approved method. In the algorithm, the signature is in the range: ...

3

Suppose you have two message-signature pairs, $(m_1, s_1), (m_2, s_2)$, where $s_i = m_i^d \bmod n$. Suppose we also know the public exponent $e$—it is usually $65537$, $3$, $5$, $17$, or some similar small integer. Then we know that $m_i = s_i^e \bmod n$, or in other words $s_i^e = k_in + m_i$ and it follows that \$\gcd(s_1^e - m_1, s_2^e - m_2) = \gcd(k_1, ...

Top 50 recent answers are included