Stack Exchange Network

Stack Exchange network consists of 175 Q&A communities including Stack Overflow, the largest, most trusted online community for developers to learn, share their knowledge, and build their careers.

Visit Stack Exchange

New answers tagged

3

Since the input sizes are fixed, length-extension attacks are not relevant, so any of the SHA-2 functions reasonably implements the random oracle model assumed by OAEP or PSS via MGF1—even the default of SHA-1 works with MGF1. Obviously it will cost slightly more to use SHA-224 or SHA-384 than to use SHA-256 or SHA-512 because SHA-224 and SHA-384 are ...


0

A session key is used to share a symmetric key over asymmetric encryption. The reason behind this is that symmetric encryption algorithms are faster than asymmetric encryption algorithms, this is also called a hybrid cryptosystem, since it combines symmetric and asymmetric encryption. The session key is generated randomly at the start of a session and is ...


0

As long as the two primes are large and random, and ideally approximately the same size, they will be suitable for a secure implementation of RSA. For an $n$-bit RSA key, it's generally safe to generate two $n/2$-bit random primes. As long as the two primes are generated randomly using a cryptographically-secure random number generator, they can be used ...


0

Defining the public and private exponents as inverses modulo φ(N), as originally done for RSA, provides a sufficient (but not necessary) condition for the decryption rule to recover the plaintext from any ciphertext. Since Carmichael’s lambda function is, by definition, the smallest number m such that $a^m \equiv 1 \pmod N$, for any integer a that is ...


0

When $n$ is the product of primes $p$ and $q$, $\varphi(n) = (p - 1)(q - 1)$ and $\lambda(n) = \operatorname{lcm}(p - 1, q - 1)$. The former multiplies $p - 1$ and $q - 1$, whereas the latter finds the least common multiple of the two. Naturally, $\forall a,b:\operatorname{lcm}(a,b) \le a\cdot b$, so we can say that $\forall n:\lambda(n) \le \varphi(n)$. In ...


7

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


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


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


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


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


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


0

Here's how to recover $e \bmod 37^2$: Pick a random plaintext $m$, and use the oracle to obtain $c = c^e \bmod n$ Compute $m_p = m^{(p-1)/(37^2)} \bmod p$ and $c_p = c^{(p-1)/(37^2)} \bmod p$ If $m_p^{37} = 1$, then try again with a different random plaintext; this is to eliminate plaintexts that don't give you as much information as they could; if you ...


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


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


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


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


0

As kelalaka hinted, the issue with particularly short plaintext in unpadded RSA is that it is subject to brute force via chosen plaintext attack. For each plaintext $m$ in the short space you suspect the enciphered plaintext to originate from calculate $c = m^e \text{ mod } n$ where $e$ is the public encryption exponent and $n$ is the public modulus. Then ...


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


0

I see four ways how to attack this scheme 1) RSA malleability Suggested in comments 2) If $e=3$ then Trivial attack exists. Hint: What is the minimal possible size of $N$? 3) If the attack is active(MiTM) Cheaper attack exists. Hint: Treat the task as a set of Oracles: $Oracle0: n \mapsto E(n)$ - If you know $(e,N)$, you can encrypt any $n$. $Oracle1: \...


0

Digging around, I found a partial answer. There is a particular case of this problem when you use \x00 as a constant. In that case, it becomes trivial to reverse the encryption (under the assumption that $e$=3), since the message becomes: m = '\x00' * 70 + m + '\x00'*70 The 00 bytes right-padding is essentially a left bit-shift of the original message (and ...


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


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


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


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


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


Top 50 recent answers are included