# Tag Info

22

The solution is simply to make sure that you have good randomness. At the size of the numbers we are considering, the probability of a repeat when using good randomness is extremely small. To make this clear, there are well over $2^{1000}$ prime numbers of length 1024. The probability of a repeat at any reasonable number of primes chosen, when using true ...

11

Obviously, good entropy is the Right Solution, however there is a mitigation possible that would help somewhat even with marginal entropy. The issue occurs if we have two different keys with the same $p$ but different $q$s; if that happens, then a third party with both public keys can factor both. What we can do is try to avoid this situation (even if ...

6

(Comments to Yehuda Lindell's answer turned to answer per request) The option to "write a fresh random 256-bit seed in every device during production" is good, in that it avoids the need for a reliable TRNG in the device. But it is not entirely without drawbacks: how do we make sure that no one knows that value, and convince others of that? Perhaps we ...

6

GCD only works if you have multiple different keys that share a prime. If the entire key is identical then GCD doesn't help you. The duplicate primes problem is normally a result of a random number generator with two characteristics. The random number is initially poorly seeded. During the key generation process the random number generator is subject to ...

5

For the problem as stated in the question, yes what's asked is possible, exactly per the method stated in the question. For textbook RSA (except with unusually tolerant decryption code), no, that's not possible. For RSA as practiced, there exists solutions or not, and it can be found on not, depending on methods and parameters. The critical differences are ...

5

This scheme suffers from a classic problem of textbook RSA which is mitigated e.g. by RSA-KEM (as outlined by kelalaka) or RSA-OAEP. When you compute $k^3\bmod N$, you'll experience that $$c=k^3\stackrel{k< 2^{256}}{\leq}\left(2^{256}\right)^3=2^{768}\ll 2^{2000}<N$$ Now remember how $x\bmod N$ works: If $x\geq N$, then you recursively compute and ...

4

What you describe is a little away from the RSA-KEM (KEM : Key Encapsulation Mechanism). As pointed out by SEjPM, in the comments, an AES-128 key when encrypted with the public modulus has almost 768 bits and this can be recovered by the cube-root attack. Here is the RSA-KEM; RSA-KEM mitigates the attack that you have. RSA-KEM for a single recipient with ...

4

This question looked due to the Cold boot attack, by Halderman et. al. Normally researchers look at some random known bit known due to the decaying of the memory. 2009 Heninger et. al Reconstructing RSA Private Keys from Random Key Bits if $\delta = .57$ fraction of the bits of $p$ and $q$ is randomly is given they can construct them. The closest article ...

4

As long as you are not wedded to RSA, here's a way that completely solves the problem (and scales to more than two targets). The general idea is that we do EC-ElGamal in a pairing friendly curve (that is, an elliptic curve that has a computable function $e(X, Y)$ that satisfies the identity $e(aG, bG) = e(G, G)^{ab}$, for any integers $a, b$ (and $G$ is the ...

4

It uses deterministic padding, i.e. padding with FF octets, finalized by a single 00 valued byte. So it is indeed RSASSA-PKCS1-v1_5 which uses EMSA-PKCS1-V1_5-ENCODE. Don't be fooled by the reference to RSA encryption in the OID for sha256WithRSAEncryption. That simply points to the modular exponentiation - in this case with the private key. PKCS#1 versions ...

3

Since this is an exercise, I'll provide the links of the articles as a hint; The linearity of the messages is first studied when $e=3$ Low-Exponent RSA with Related Messages by Don Coppersmith, Matthew Franklin, Jacques Patarin, Michael Reitert, EUROCRYPT 1996: Advances in Cryptology — EUROCRYPT ’96 pp 1-9 A more general case, where $e$ is not limited to ...

3

I am writing an application that involves checking to see if data has been created by me. That's known as verifying data that was signed. It is good practice. I do this by encrypting the data with the private key on my server, and then decrypting it using the public key on the client. That's where it gets wrong. The server must sign with the private key,...

2

Libsodium is written/implementable in C++, C and Python. It implements lots of crypto systems, such as public key cryptography. Here is the intro in the docs: https://libsodium.gitbook.io/doc/

2

You are close but not exactly. In short, RSA is a trapdoor permutation. Let $(n,e)$ is a RSA public key, then $y = f(x) = x^e \bmod n$ is a trapdoor permutation. RSA is a permutation since the function $f:\mathbb{Z}_n^*\to \mathbb{Z}_n^*$ is bijective. RSA is a trapdoor permutation. Normally you can find the inverse a permutation if it is given ...

2

Is step #3 (verifying the EMSA-PKCS1-v1_5 padding) important to the security of the system? Yes. That's paramount for small RSA public exponent $e$. For $e\in\{3,5,7\}$, the easily computed integer $s=h^{(e^{-1}\bmod2^{254})}\bmod2^{256}$ is an acceptable signature for any message with an odd SHA-256 hash $h$ (that is about one message out of two). The ...

1

Sender encrypts the message with private key and sends his/her public key and the receiver decrypts by using sender's public key and vice versa. No, you cannot encrypt (for confidentiality) using a private key; anybody with the public key can decrypt after all. Now how this is RSA or AES? Because the message should be encrypted by receiver's public key ...

1

(in RSA) the encryption process is sort of like a substitution cipher... That's the case in RSA encryption as explained in some introductory courses, where several small blocks of text are enciphered independently, often with a public modulus of only a few decimal digits (perhaps 2 to 8). RSA encryption as actually used works quite differently: The public ...

1

I think Crypto++ will help you. This is a cryptography library implemented in C++. Its homepage: Crypto++ Library.

1

So, you're given the exponents (and the ciphertext), and are expected to recover the modulus? That's certainly not the standard way of using RSA. It turns out that the necessary and sufficient conditions on $p, q$ is that $p-1, q-1$ are factors of $ed-1$; hence we know that $p, q \in \{ 3, 5, 11, 17, 41 \}$ (as those are the primes that meet this criteria),...

1

The comparison can be made according to know attacks and their timings. Your source doesn't provide a reference and date backs to 2015, so that is not a good site as keylength.com. The current values of this answer is taken for 2019. ECC For ECC 128 bit security means we need 256-bit curves due to the generic discrete log attacks that have \$\mathcal{O}(\...

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