# Tag Info

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 ...

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

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 ...

10

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 ...

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

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

The question asks how to systematically pick the public exponent $e$ in RSA. I'll stick to public modulus $N$ that is the product of exactly two distinct odd primes $p$ and $q$, but the choice of $e$ is not fundamentally different in multiprime RSA. What's an acceptable public exponent $e$? The public exponent in RSA should be an integer $e>1$ with ...

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

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

Rather than making an overly long question even longer, I post this as an answer. As part of the update process of the French security recommendations linked in the question, I suggested (June 2013) a waiver for the requirement/recommendation that $e>2^{16}$ when using a padding scheme with a security proof. It was kindly refused (within 6 weeks), with ...

8

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 ...

8

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 ...

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. ...

8

We want a non-trivial factorization of a moderate odd integer $n$ into positive integers $p$ and $q$, knowing that such factorization with $|p-q|$ suitably small exists. Perhaps the most elementary method answering the question is trial division by integers starting at $\lfloor\sqrt n\rfloor$, going down. This succeeds after checking divisibility of $n$ by ...

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

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

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

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$.

7

If $p$ and $q$ are 1024-bit primes, then by definition of the bit size of an integer (at least, a prime in a cryptographic context with glimpses of RSA), $2^{1023}\le p<2^{1024}$ and $2^{1023}\le q<2^{1024}$. Thus their product $n=pq$ verifies $2^{2046}\le n<2^{2048}$, and $n$ is a 2047-bit or 2048-bit integer. We show by exhibition that both cases ...

6

This expands CodesInChaos's comment into an answer. Forward Secrecy (that is, maintaining confidentiality of messages enciphered before compromise of the long term key) can be achieved in a protocol using a public-key signature scheme with a long-term public key, and a public-key encryption scheme with a per-session key; but in the case of RSA signature and ...

6

Start by reading the paper. They have an entire section on defences: it is Section 11, Mitigation, pp.46-48. As far as software countermeasures for RSA specifically, they mention blinding as a good defence. Blinding is a standard defence against many kinds of side-channel attacks, and it is apparently effective against acoustic cryptanalysis as well. ...

6

A possible RSA variant uses: some odd exponent $e>2$ (that can be $e=3$ or $e=2^{16}+1$ as customary in standard RSA); $p$ and $q$ distinct large random primes, with $\gcd(e,p)=\gcd(e,p-1)=\gcd(e,q-1)=1$; $N=p^2\cdot q$; some $d$ computed such that $d\cdot e\equiv 1\pmod{\operatorname{lcm}(p,p-1,q-1)}$; public-key function $x\to x^e\bmod N$; private-key ...

6

Well, one reason to hash the data before signing it is because RSA can handle only so much data; we might want to sign messages longer than that. For example, suppose we are using a 2k RSA key; that means that the RSA operation can handle messages up to 2047 bits; or 255 bytes. We often want to sign messages longer than 255 bytes. By hashing the message ...

6

We are dealing here with two assumptions and we always refer to $N=pq$ the product of two $n$ bit primes $p$ and $q$. The one is factoring and the second is the so called RSA assumption which is a formalization of "inverting the RSA function is hard". These two assumption can be described as follows: Factoring assumption: There exists no probabilistic ...

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