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

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

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

9

You don't need to know $m$. You know $m^3$ modulo each modulus, which is sufficient. You want to find: $$c \equiv m^3 \pmod{n_b}$$ $$c \equiv m^3 \pmod{n_c}$$ $$c \equiv m^3 \pmod{n_d}$$ Because $n_b$, $n_c$, $n_d$ are pairwise coprime (assume they have no common factors) a solution must exist. The Wikipedia page has a nice explanation of the algorithm ...

9

In RSA, the bit size $n$ of the public modulus $N$ is often of the form $n=c\cdot2^k$ with $c$ a small odd integer. $c=1$ ($n=512$, $1024$, $2048$, $4096$.. bit) is most common, but $c=3$ ($n=768$, $1536$, $3072$.. bit) and $c=5$ ($n=1280$..) are common. One reason for this is simply to limit the number of possibilities, and similar progressions are found ...

9

The advice to avoid $e=3$ comes down primarily to superstition, historical inertia, and general caution, rather than anything with a solid technical basis. Historically, some of the early schemes that used $e=3$ were subject to attack. At the time, many folks drew the conclusion that this means $e=3$ is insecure. However, we now know that that conclusion ...

9

If the RSA keys were generated randomly, then it is inconceivable that two different devices would happen to pick the same key. Taking 2048 bit RSA keys as an example, there are approximately $2^{1014}$ 1024 bit primes; if we consider them pairwise (and realise that about half the pairs yield a 2047 bit number), that means there are about $2^{2026}$ RSA ...

9

It is true that elliptic curves allow the same security with smaller key sizes. However, the size is not the only important aspect. Familiarity of algorithm, ease of implementation, performance, how many independent implementations exist, etc. affect how widely algorithm is implemented. For Elliptic Curves, like many other technologies one factor slowing ...

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

8

I don't believe a lower bound has ever been proven for the "fewest" number of bits needed. Coppersmith showed, however, how given either the $n/4$ least or $n/4$ most significant bits of $p$ where $n$ is the size of the modulus $N=pq$, $N$ can be efficiently factored. Additionally, given the $n/4$ least significant bits of $d$, one can reconstruct $d$ (and ...

8

Those appear to be based on the complexity of the General Number Field Sieve, one of the fastest (if not the fastest) classical factoring algorithms. I confirmed this in Mathematica. Here is the complexity for the GNFS (pulled from the linked Wikipedia article): $$\exp\left( \left(\sqrt[3]{\frac{64}{9}} + o(1)\right)(\ln n)^{\frac{1}{3}}(\ln \ln ... 8 A proof of P = NP would prove that one-way functions do not exist. That in turn would imply, that almost no secure cryptographic primitives can exist according to the accepted definitions of security. (No symmetric encryption, no MACs, no pseudorandom generators, no signature schemes, ...) However, it would just mean that no scheme can be provably secure. ... 8 A trapdoor function is a function that is easy to perform one way, but has a secret that is required to perform the inverse calculation efficiently. That is, if f is a trapdoor function, then y = f(x) is easy to compute, but x = f^{-1}(y) is hard to compute without some special knowledge k. Given k, then it is easy to compute y = f^{-1}(x, k). ... 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 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 ... 7 The letters d and e are just a notation -- what matters is that there are two exponents, each undoing what the other does, and making one public does not intrinsically reveal the other. By tradition, the one made public is called e. However, there is a twist: the exponent that is not made public, i.e. the private key, can be really private only if it is ... 7 If you compare DSA with SHA-256 and a 2048 bit group modulus p, to RSA with SHA-256, a 2048 bit modulus n and public exponent e = 65537, on you will at least perform the following operations: DSA g^{u_1}y^{u_2} - 2*256 squares \mod p, up to on average 2*128 multiplications \mod p, depending on implementation optimizations. RSA s^e - 16 ... 7 In practice, asymmetric algorithms like RSA are usually used for key transport. In other words, instead of a true message, they are used to encrypt a secret key for a symmetric cipher. That symmetric cipher key is used to encrypt the actual message, and that could be gigabytes, depending on the algorithm. Standards like TLS, PGP, and S/MIME use RSA in ... 7 I suspect that the meet-in-the-middle attack you have in mind is what is presented in this answer (or something similar). If so, then it's not actually correct to say "the only requirement is that the message be a product of 2 numbers of the same magnitude"; the message needs to be a product of two numbers of the same small magnitude. For example, the ... 7 Presumably, it's because they rounded it down to a nice round number of bits. Nobody's going to use an 86.76611925028119 bit key in practice, but an 80-bit key is plausible. Besides, the 86.whatever bit symmetric key length is only approximate, anyway: even using the GNFS, implementation details could easily swing it several bits either way, and of course, ... 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

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

7

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

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

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

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

6

Using powers of two is traditional. It also has a few implementation benefits for very constrained architectures: it saves a few instructions. This indirectly implies that some implementations are not able to process RSA keys whose size is not a multiple of 32 or 64, meaning that if you want maximum interoperability, you should not use other key sizes as ...

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