Tag Info

Hot answers tagged

13

$\phi(n)$ is the order of the multiplicative group of the numbers in $\mathbb{Z}_n$. $\phi$ is known as Euler's totient function. A consequence Lagrange's theorem is that any element of a group, raised to the order of the group is equal to the identity element. So, using $\phi(n)$ ensures that decryption works. Since $ed\equiv 1\bmod{\phi(n)}$, we can say ...


12

No, there is no known test that we can run on a 2048 bit composite number that would indicate whether it was the product of two primes, or whether it was the product of more than two primes. About the closest we can get is a zero knowledge proof; we know how someone (who does know the factorization) can run an interactive proof with us that can demonstrate ...


11

I thought about this and done a bit of research and the answer is no. The problem is the gap between the difficulty of factorisation versus prime generation isn't really large enough at the scale of primes/moduli we can work with. By 1588 the largest prime discovered was 524287 and that was due to Pietro Cataldi. This was a prime generated by a single ...


10

Ricky's link answers your main question in the comments (that knowing the private key is equivalent to knowing the factorization of $N$). But your "attack" is unfortunately part of a class of properties which might appear insightful at first, but which eventually boil down to something like this: "find integers $(m,k)$ such that $m+kn$ is a perfect square" ...


10

Where does the $\phi(n)$ part come from? Well, the actual requirement is that, if $n = pq$ and both $p$ and $q$ are prime, we have: $de \equiv 1 \mod p-1$ $de \equiv 1 \mod q-1$ The first ensures that RSA encryption, followed by RSA decryption, will obtain the original value modulo $p$. The second ensures that RSA encryption, followed by RSA ...


10

The security of every single cryptographic algorithm(*) of any kind is ultimately based on: "many people looked at it for a long time and did not find a way to break it". Security proofs boasted by some algorithms are quite useful but they don't actually prove security, they move it (a security proof is a reduction to another problem which has to be assumed ...


9

Actually, that was proposed here back in 1998 (sorry, an electronic version of the paper does not appear to be on the web) -- the author claimed a modest speedup in the private operations. However, that speed up would appear to be about the same if you just did "multiprime RSA", that is, selected an RSA modulus of the form $pqr$ for three distinct primes ...


9

The first observation in the question boils down to: in textbook RSA, the encryption of $N-M$ instead of $M$ yields $N-C$ instead of $C$. This is a special case of a more general property of textbook RSA, that the encryption of $M\cdot M'\bmod N$ yield $C\cdot C'\bmod N$, whenever enciphering $M$ yields $C$ and enciphering $M'$ yields $C'$; combined with ...


9

In addition to the performance problems poncho already mentioned when using RSA signatures without hashing I just want to add on the security warning of poncho: Reordering If you have a message $m>N$ with $N$ being the RSA modulus, then you have to perform at least 2 RSA signatures as $m$ does not longer fit into $Z_N$. Let us assume that it requires ...


9

Actually, that's an expected result since $65 \equiv 10 \pmod{55}$. You should choose $m < n$ to avoid this problem.


9

No, there is no specific vulnerability associated to choosing $p$ and $q$ with size differing by $i$ bits (or $2\cdot i$ bits as in the statement) for small $i$. However, if $i$ gets too big: That improves the odds that ECM will manage to factor $n$ for some fixed size of $n$, and at some point ECM will become the best algorithm; this is the case if $i$ is ...


9

If we consider an RSA modulus $N$ of $n$ bits ($n=2048$ in the question) product of $k$ primes of about $n/k$ bits, how high can be $k$ without loosing security? That's a problem studied even before Multiprime-RSA was named, with no definitive answer other than: we can't err on the unsafe side with $k=2$. Why would we want $k>2$? For classical ...


8

No, it not possible to attack RSA (and practical modulus size) with a WalkSat derivative, as far as we know, or using the algorithm in the question. Problem with that algorithm is: in order to have a sizable/constant rate of success as $n$ increases, we have to repeat steps 2 and 3 not the stated $t\cdot m^2$ times, but rather $t\cdot 2^m$ times. That's ...


8

It doesn't become vulnerable; instead, it becomes impossible to decrypt uniquely. Let us take the example you give: $N=65$ and $e=3$. Then, if we encrypt the plaintext $2$, we get $2^3 \bmod 65 = 8$. However, if we encrypt the plaintext $57$, we get $57^3 \bmod 65 = 8$ Hence, if we get the ciphertext $8$, we have no way of determining whether that ...


8

The problem is a very old one going back at least as far as the late 1940's early 1950's and has been shown to exist with Quantum Key Exchange as well. You need to think of it in terms of entropy down to heat pollution where a coherent signal energy steps down due to inefficiency via various transducers to what is basically thermal noise where the noise ...


8

When encrypting something with RSA, using PKCS#1 v1.5, the data that is to be encrypted is first padded, then the padded value is converted into an integer, and the RSA modular exponentiation (with the public exponent) is applied. Upon decryption, the modular exponentiation (with the private exponent) is applied, and then the padding is removed. The core of ...


8

There's no real difference between $p$ and $q$ in RSA. It looks like OpenSSL just has the agreement "$p$ has to be bigger than $q$" for conveniences. One of the numbers has to be bigger than the other (otherwise they would be the same number, and $p = q$ is very bad in RSA). Just use two examples: $p = 13$ and $q = 11$. $p$ is bigger than $q$, all right. ...


7

I don't think idea 1 can be made to work at all. The main point is that in order to generate a correct secret decryption key, the key generator must know the order of $\mathbb Z^*_n$, i.e., the totient of the modulus $n$. The generator knows that $n=p \cdot q$, where it believes that $p$ and $q$ are primes, and so it believes that the totient is ...


7

@pg1989 has not only the right answer, but the only answer if you assume the goal is to have multiple RSA encryption exponents that correspond to the same decryption exponent. $$e_1 * d \equiv 1\ (\mathrm{mod}\ \phi(N))$$ $$e_2 * d \equiv 1\ (\mathrm{mod}\ \phi(N))$$ $$(e_1 - e_2) * d \equiv 0\ (\mathrm{mod}\ \phi(N))$$ But since $d$ is relatively prime ...


7

In RSA as usually practiced (encryption or signature per PKCS#1, signature per X9.31, ISO/IEC 9796-2, FIPS 186), it is NOT necessary, or even common, to require $n=p⋅q$ with $p=2⋅p′+1$ and $q=2⋅q′+1$ with $p'$ and $q'$ huge primes, as stated in the question. IF that's done, it ensures that: any small odd $e>2$ (including the common $e=3$ and $e=65537$) ...


7

As long as you use a secure padding mode (i.e. -pkcs or -oaep, not -raw). The default padding mode for openssl rsautl is -pkcs (i.e. PKCS#1 v1.5), so you should be OK. That said, OAEP is recommended over PKCS#1 v1.5 padding, so you might want to use the -oaep switch.


7

When $n$ is prime, solving for $e$-th roots modulo $n$ is easy, since it suffices to compute $d = e^{-1} \pmod {n-1}$ and then $s = m^d \pmod n$. If $n$ is not prime, but is instead a RSA modulus (a composite integer that is the product of two big primes), then the problem becomes apparently hard (in the sense that we don't have a clue how to do it ...


7

The two last equations don't directly give you the value of $C_i$, they are telling you the values of the remainder of Ci when divided by $P$ and $Q$. You then use the Chinese Remainder Theorem with this information to produce the value of $C_i$ (modulo $N$) that you are looking for. See en.wikipedia.org/wiki/Chinese_remainder_theorem (there is an algorithm ...


7

If we remove from RSA the requirement that the factors $p$ and $q$ of the public modulus $n=p\cdot q$ are prime, and instead allow composites, then depending on the definition of RSA used, the resulting cryptosystem works in the sense of allowing decryption either: almost not (only for few messages or exceptional choices of $p$ and $q$); that's if we ...


7

I had a similar problem, and it took me a long time to figure out all the math, as some of the proofs can be rather terse. So, I took it upon myself to write a full explanation of how to factor N, without all the symbols and relying on a bit less prior knowledge. This is an application of the shared modulus attack explained by Boneh in his analysis of RSA ...


7

How is it possible to memorize or remember a key that is about 4000 bits long? One could reasonably ask the same question about AES: how is it possible to remember a key that is 128 bits long? The answer is: "it doesn't really matter, because no one actually tries to remember a sequence of 128 random bits, much less 4000 bits anyways". Instead, we ...


7

Yes. Modern cryptosystems are designed and analysed under the assumption that the key is never used for anything else. If you use your encryption keys for digital signatures, you are violating that assumption, and it is very easy to construct schemes where this violation will compromise security. It is possible to construct schemes that can use the same ...


7

Selecting a small $d$ is known to be insecure. Wiener has shown in 1990 that if $\log d \leq \frac14 \log N$, the private exponent $d$ can be reconstructed from the public key $(N,e)$. If you're interested in making the private computational cost cheaper, then I would suggest that RSA is not the best solution; I would recommend you start looking at ...


7

Yes, they are (deterministically) equivalent. The original RSA paper (Section IX.C), working off Miller's results (Theorem 3), showed how knowing the secret exponent $d$ was probabilistically equivalent to factoring $n$. Later, using more advanced techniques, Coron and May showed how to deterministically reduce finding $d$ to factoring $n$.


6

Directly applying the RSA-function to a message is not secure in real life. The function leaks all kinds of information about the underlying plaintext and is particularly vulnerable to active attacks (where the attacker might be able to learn something about some related message also encrypted under RSA, and use this to learn what the original message was). ...



Only top voted, non community-wiki answers of a minimum length are eligible