Hot answers tagged rsa
20
The public key blob doesn't consist of just the numbers that make up the public key: it begins with a header that says “this is an SSH public key”. The repeated prefix encodes this header.
RFC 4254 specifies the encoding of public key in SSH key format.
The "ssh-rsa" key format has the following specific encoding:
string "ssh-rsa"
mpint e
...
17
By definition you cannot encrypt values greater than the modulus in RSA, because the plaintext is immediately reduced modulo $n$ which loses information. This is because textbook RSA works in the $\mathbb{Z}/n\mathbb{Z}$ congruence ring, so from RSA's point of view, as long as two values have the same remainder modulo $n$, they are effectively equivalent. So ...
14
From the definition of the totient function, we have the relation:
$$\varphi{(n)} = (p - 1)(q - 1) = pq - p - q + 1 = (n + 1) - (p + q)$$
It then easily follows that:
$$(n + 1) - \varphi{(n)} = p + q$$
$$(n + 1) - \varphi{(n)} - p = q$$
And you know from the definition of RSA that:
$$n = pq$$
Substituting one into the other, you can derive:
$$n = p ...
9
The main difference is that Pohlig-Hellman is a symmetric cypher, while RSA is a public key system. This is because, with Pohlig-Hellman, anyone who knows the encryption key $e$ can compute the inverse operation (because the 'decryption' key $e^{-1} \bmod p-1$ is easy to compute), while the RSA, someone who knows the encryption key $e$ (but not the ...
8
Using $e\ne65537$ would reduce compatibility with existing hardware or software, and break conformance to some standards or prescriptions of security authorities. Any higher $e$ would make the public RSA operation (used for encryption, or signature verification) slower. Some lower $e$, in particular $e=3$, would make that operation appreciably faster (up to ...
8
Proving $\gcd(e, e_2) = 1$ is easy; all you need to do is rely on the property
$\gcd(e, e_2) = \gcd(e, e-e_2)$
Now $e$ and $e_2$ differs in a single bit (because Peter flipped one bit in $e$ to form $e_2$), and hence $|e - e_2|$ is a power of two (the sign of which depends if Peter flipped a zero bit or a one bit), and hence has $2$ as its only prime ...
8
Yes, this thinking is correct; there is no requirement that the public exponent $e$ to be random. After all, it doesn't matter whether $e$ can be guessed by an attacker; we'll be including that value in the public key anyways.
Common practice is currently to use the fixed value $65537 =2^{16} +1$ for $e$. Any odd value of $e > 1$ will work; however, ...
7
Vanilla textbook RSA does not include "padding and stuff", the term "textbook RSA" generally refers to simply encoding a plaintext message as an integer and raising it to an exponent. Implementing this is pretty easy, just follow the steps outlined on Wikipedia. You can easily translate those steps into some given programming language.
Based on the rest of ...
7
No, the public and private exponents will never be the same for real (that is, not toy) RSA keys.
The public exponent is almost always be deliberately chosen as a small value (with 65537, 3 and 17 being the most popular choices). In contrast, the private exponent will always be a huge value; always at least $(p-1)/e$ (where $p$ is the larger prime factor ...
7
Is this usable? Or does the generation of the modulus outweigh any
gains in the difference in signing time?
No, it does not work. The generation cost itself isn't too important, because signing any one nonce doesn't help the client sign any other nonce, so you can just use a single key all the time (if you had to create a new keypair for every puzzle, ...
7
No, it's not safe to seed a PRNG with the hash of a password, then generate a key from that PRNG. That is especially bad with DSA and shared parameters $(p,q,g)$, and only slightly less unsafe for RSA, or DSA with per-key parameters $(p,q,g)$. Two essentials things are missing: some slow step, and salt.
If the proposed procedure was applied, all there is to ...
6
No.
The challenge for RSA-155 (which is 512 bits) was broken in 1999. This took 6 months on pretty advanced hardware to break at the time, which works out to 8000 MIPS years. It should be much less today.
FYI, RSA 768 took just under 3 years.
6
OpenSSL private key format, for RSA, follows the ASN.1 syntax given at the end of PKCS#1 (the structure is then encoded with DER, then Base64, and PEM header and footer lines are added). This is easy if you know these formats, but, in practice, you will be happier if using a library which does the encoding for you. For instance, OpenSSL (the library) lets ...
6
If you know $\phi(n)$ it's trivial to calculate the secret exponent $d$ given $e$ and $n$.
In fact that's just what happens during normal RSA key generation. You use that $e \cdot d =1 \mod \phi(n)$, and solve for $d$ using the extended Euclidian algorithm.
Wikipedia about RSA key generation:
Determine $d$ as:
$d = e^{-1} \mod \phi(n)$
i.e., $d$ is ...
6
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 ...
6
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 ...
6
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 ...
5
The other answers explain why you shouldn't take shortcuts like this and why it won't provide much of a speedup anyway. As for an actual attack, here's an obvious one: brute force.
With the parameters you gave, there are only $\binom{309}{3} = 4869634$ possible values for d, which is small enough to easily check every value.
5
Well, reusing a key isn't a problem; after all, RSA keys are generally used many times.
However, if you fix the padding, there does exist one other potential problem; message malleability.
To example, suppose Alice sends two messages to Bob, $X_1, X_2$ and $Y_1, Y_2$. To send these, Alice actually sends:
$E(X_1), E(X_2)$
$E(Y_1), E(Y_2)$
Now, Eve can't ...
5
It's not possible.
The number of primes smaller than $x$ is approximately $\frac{x}{\ln x}$. Therefore the number of 512bit primes (approximately the length you need for $1024$ bit modulus) is approximately $\frac{2^{513}}{\ln 2^{513}}-\frac{2^{512}}{\ln 2^{512}} \approx 2.76×10^{151}$.
The number of RSA moduli (i.e. pair of two distinct primes) is ...
5
A slightly more efficient method to perform decryption would be:
Compute $r^e = (y^d)$
Find the multiplicative inverse $r^{-e}$ of $r^e$ modulo $n$
Compute $m = (r^{-e} \cdot z)^d = (r^{-e} \cdot r^e \cdot m^e) ^d$
This has two computations of $x^d$ for some $x$; your method has three.
On the other hand, this doesn't address your question; if $r^{-1}$ ...
5
RSA without padding is also called Textbook RSA.
The question why RSA without padding is insecure has already been answered
in this question.
We can fix a few issues by introducing padding.
Malleability: If we have a strict format for messages, i.e. that the first or last bytes contain a specific value, simply multiplying both message and ciphertext will ...
5
For RSA, we generally count bits rather than bytes; with RSA, we say a modulus is $k$ bits long if $2^{k-1} \le n < 2^k$
There's no proof involved, because it is not a mathematical statement, instead, it is how we define what a $k$ bit modulus is.
Another way of looking at it is if we take the modulus, and count the bits, from the highest bit that is ...
5
There are no known implications of the ABC Conjecture to RSA. The ABC problem doesn't have even a superficial resemblance to the security of RSA.
(The only point of connection is the fact that they both relate to prime numbers, but that is extremely thin. Much of number theory can say it is somehow related to prime numbers. It'd be like assuming that ...
5
PSS is harder to implement because it uses randomness -- randomness is hard on many embedded systems like smart cards.
The most proclaimed advantage of PSS is that it has a "security proof" with, apparently, a rather tight reduction (see this page for some references). Security proofs are not an easy subject; the proof for OAEP (the encryption padding which ...
5
None.
When enciphering any small set of values (including a fair coin flip, a byte, even a small password..), unpadded RSA (or RSA with any padding that does not include randomness) is a terminally weak encryption method: the adversary can enumerate the possible plaintext values, encrypt them using the public key, and check against the ciphertext to ...
5
Yes, this is textbook RSA, so by definition:
$0^e \equiv 0 \pmod{n}$
$1^e \equiv 1 \pmod{n}$
$(n - 1)^e \equiv (-1)^e \equiv -1 \equiv n - 1 \pmod{n}$
(since $e$ must be odd as $\varphi{(n)}$ is even and thus $2$ has no modular inverse modulo $\varphi{(n)}$)
This is (obviously) bad since an observer can immediately deduce the plaintext for those ...
5
Well, think about it this way. If breaking one encryption with brute force will take longer than the lifetime of the universe, are you any safer with an encryption scheme that will take twice the lifetime of the universe? No. The first encryption cannot be broken. Adding a second encryption just adds computation overhead with no real benefit.
Think about it ...
5
INT-CTXT and INT-PTXT are usually on considered for private-key encryption. For public-key encryption, no correct encryption scheme can satisfy those requirements. (Proof: The adversary can run the encryption algorithm on an arbitrary message and submit it as its output. Since it made no queries to its encryption oracle, this ciphertext violates both ...
5
The $2^{16} + 1$ exponent is really meant for use in real life systems, in which public keys are expected to be considerably larger than that. I guess CrypTool assumes this is the case, as you would expect, really.
That said, if $\gcd{(e, \varphi{(n)})} = 1$, then $gcd{(e ~ \mathrm{mod} ~ \varphi{(n)}, \varphi{(n)})} = 1$ by definition, so such an $e$ will ...
Only top voted, non community-wiki answers of a minimum length are eligible
