# Tag Info

## Hot answers tagged rsa

52

Asymmetric encryption is vastly inferior to symmetric encryption. That is, in all respects, except one -- being asymmetric. When that property is needed, there's no way around it, obviously. Asymmetric encryption is much slower. It is much more susceptible to showing recognizable patterns of some kind given non-random input. You need much larger key sizes ...

13

The cold boot attack can be performed on any encryption scheme as long as the keys reside in memory. For full-disk encryption (FDE) with symmetric algorithms like AES, you will need to take the key out from the TPM, where you will be susceptible to a cold boot attack. Though the TPM is capable of RSA encryption and decryption, for FDE RSA has problems, in ...

9

TPMs do not perform the actual encryption used for full disk encryption. All they do is encrypt the key while the system is powered off or in a suspended state. The key is decrypted and passed once to the operating system over the LPC bus, which then keeps it in memory while encryption is performed. The reason a TPM would be a poor choice for securely ...

9

If you reuse the same key material for different algorithms, you rely not on the security of any one algorithm individually, but on the security of the composition of the two algorithms simultaneously. For a particularly egregious example, if you use the same RSA public key for RSASSA-PKCS1-v1_5 and for HMAC-SHA256, the results might be entertaining. It ...

6

You can't have two different public keys for the same RSA private key. That's just not how RSA works. Well, almost. There's a minor technical loophole, and it's the fact that RSA has equivalent keys. In particular, the public keys $(n, e)$ and $(n, e + \lambda(n))$ are equivalent, in the sense of producing the same ciphertext for the same (padded) ...

5

Is it possible to figure out it's value when $e$ is not bruteforce-able? It depends. First note that knowing you can easily factor $n$ given that you also know $\varphi(n)$ (2-prime case). Next note that $\mathbb Z_n^*\cong\mathbb Z_p^*\times \mathbb Z_q^*$ (by the CRT), this means that doing component-wise operations on the pairs from the latter groups is ...

5

OpenSSL is not being dumb and there is a reason the keys have different OIDs, but it's unrelated to the key data — it's the key metadata. The metadata describes the key. Specifically, the ASN.1 type above is PrivateKeyInfo and the difference is in the AlgorithmIdentifier. From an organizational perspective where you have to keep track of two RSA ...

5

For the private key it may or may not matter to code using the key, but for the public key especially in a CSR or cert the algorithm identifier is visible and can matter. OpenSSL generates a CSR containg a public key which is automatically extracted from the private key, including the AlgId, which is normally copied to a cert where the AlgId in the public ...

3

The cost of computing $x^e \bmod n$, which is the bottleneck in any RSA-based cryptosystem, is $\lfloor\log_2 e\rfloor$ squarings and $H(e) - 1$ multiplications modulo $n$, where $H$ is Hamming weight.* Since $e$ is required to be coprime with $\operatorname{lcm}(p - 1, q - 1)$, the most efficient possible choice is $e = 3$.† Originally, the 1977 RSA ...

3

Although PKCS1's ASN.1 is a quite common representation of RSA keys, it is not the only one used (and certainly not the only one possible). The standards for XML digital signature and encryption unsurprisingly use XML not ASN.1 for data structure: https://www.w3.org/TR/xmldsig-core1/#sec-RSAKeyValue The standards for JSON Web Signature and Encryption (...

3

Shor's algorithm works by using quantum magic to compute a period of $f\colon x \mapsto a^x \bmod n$ for random $a$; if it gives $2t$ so that $a^{2t} \equiv 1 \pmod n$, and if $a^t \not\equiv -1 \pmod n$, then $\gcd(a^t \pm 1, n)$ is a nontrivial factor of $n$. (Otherwise, repeat with another $a$.) If $n = p q r$ and $\gcd(a^t \pm 1, n) = p$, then you can ...

3

Your message has to be smaller than n to be correctly encrypted / decrypted with RSA.

3

This is essentially because the best known generic algorithms for discrete logarithm, e.g., baby step giant step, have complexity $$O(\sqrt{G})=O(2^{n/2})$$ where $n$ is the number of bits to represent the elements of the elliptic curve group $G$. If the eliptic curve group is carefully chosen, that is. So, avoid anomalous curves, for example.

3

As Ilmari said, coming up with the unique $N, e, d$ is impossible (as that are literally an infinite number of possibilities). However, if you're just interested in one possible set (which might not be the one that was actually used to generate the numbers initially), then below is one approach. Note: while it is feasible, it may be a bit more complex than ...

3

In general, you can't do that. You have one equation and two unknowns (not three, since $d$ is uniquely determined by $n$ and $e$, even if actually computing it without knowing the factors of $n$ is difficult), so the solution will in general not be unique. Of course, you could guess that $e$ might be one of the common values (e.g. 3 or 65537) and try to ...

2

By narrowing the space of messages and ciphertexts you are willing to consider to a tiny fraction of fewer than $1/2^{1000}$ of them, you cannot prove that an algorithm for breaking this translates to an algorithm for computing cube roots modulo $n$ in general. Consequently you can't rely on the decades of work that have been put into failing to find a way ...

2

Yes, it can. Quoting the document of DJB: "Post-quantum RSA" by Daniel J. Bernstein, Nadia Heninger, Paul Lou and Luke Valenta, which forest has linked to: If $n$ is a product of more primes, say $k \ge 3$ primes, then the same speedup becomes even more effective, using $k$ exponentiations with ($1/k$)-size exponents and ($1/k$)-size moduli. Prime ...

2

Shor's algorithm finds the prime factors of any integer, regardless of the number of primes. This is explained in the Wikipedia article, which describes how the algorithm takes an odd integer and finds another integer which divides it. If the composite number is not a semiprime, then you just run Shor's algorithm on the result again to get another integer ...

2

No, it is not possible. If it were, then RSA would be insecure; the same way to recover $e$ from $m_1, m_1^e \bmod n$ would be able to recover the private key $d$ from $c_1, c_1^d \bmod n$ (as that's the same problem, only using different symbols).

2

No, there is no known way to recover $d$ using an Oracle that, given $m$, returns $m^d \bmod n$; there is also no proof that such a method does not exist. Such a method would imply that the RSA problem (which is, given $m^e \bmod n$, recover $m$) is equivalent to the factorization problem (which knowledge of $d, e$ would allow you to solve); it is unknown ...

2

In any RSA-type cryptosystem, a public key necessarily has a modulus $n$, and sometimes has an exponent $e$ if it's not prescribed by the cryptosystem. Sensible cryptosystems like RSA-KEM can prescribe $e = 3$, but some defective standards, based on mistakes like RSAES-PKCS1-v1_5, may require $e$ to be $e = 65537$ or larger and may allow $e$ to vary. A ...

2

Also Can it be prevented If I store the Public key in a certificate store? Well, an adversary could probably just overwrite that entry and mount the same attack as before. Now I have a problem, what if someone's signs the license file content with entirely new set of private\public key pair. What you have stumbled across is the "trust problem" of public ...

2

There is no standard definition of "same" when applied to cryptographic keys. There is a precise definition of equivalent keys: keys which always yield the same effect when used for their designated usage, e.g. encryption, decryption, signature generation or verification. For example, in DES, low order bits of key bytes play no role, thus 0123456789ABCDEF (...

1

If you use the same padding on the same messages, sent to multiple different public keys, then you have satisfied the criteria of the Håstad attack. Randomizing the padding as in OAEP means that you don't use the same padding for each message. Even better, in a modern system like RSA-KEM, there's no ‘padding’ per se, or even any ‘message’ involved directly ...

1

It depends on what you would use the RSA algorithm for since a one-time pad (assuming you implement it correctly) should achieve perfect secrecy, which means its ciphertext cannot be cracked. RSA is one of the first public-key cryptosystems that can also be considered as secure when you are using large enough primes. So to answer your question, it cannot be ...

1

I'm not going to add any analysis, but just some RFC quotes and timelines about RSA signing ('signature scheme with appendix'), PKCS #1 v1.5 and PSS ('probabilistic signature scheme') February 2003 Users encouraged to move away from RSASSA PKCS #1 v1.5 in RFC 3447 PKCS #1: RSA v2.1, §8: Signature schemes with appendix, p. 36 Two signature schemes ...

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