Hot answers tagged

15

Are there other public key systems that do not have this property? A more cogent question might be "are there any public key systems other than RSA that does have this property?" In particular, I'm calling "this property" the idea that you can swap the public and private keys and remain secure (which you can do with RSA, as long as you select large public ...


8

That's correct. In some cases, you could, if you really wanted, make a public key equal the private key. It would completely negate the benefit of using a public key cryptosystem, though, because access to the public key would imply access to the private key. It would turn it into a crappy symmetric scheme. As noted in comments, most common RSA ...


4

Is there some measure of the total amount of entropy bits needed to make a single 4096 bit RSA key? Well, there are two relevant attacks against RSA: The attacker uses NFS to factor the modulus The attacker scans through the possible entropy inputs that possibly generated the public key, and for each such input, generates the corresponding RSA public key, ...


4

There is no minimal message size. Even an empty message can be securely encrypted, i.e. the ciphertext is indistinguishable from a different encrypted message, as long as the encryption key remains secret. Can you describe exactly what are want to achieve? Where will the secret key come from? Even though minor optimizations are possible with very short ...


3

Whenever you see the letters ECB, you should run away screaming. This is a telltale sign that something has gone terribly, horribly wrong. The code fragment you quoted implements what we sometimes call ‘textbook RSA’, which is a polite way to discreetly announce to the cocktail partygoers that you are desperately in need of a professional cryptographer. ...


2

This is standard trial-division algorithm which for some reason starts at $\sqrt{N}$ instead of at $2$ with the trial-divisors. Yes, it is functionally correct and will always find a non-trivial factor for composite numbers. However, if $N$ has more than two prime factors, this will only find composite factors if the prime factors are balanced. This is as ...


2

According to your link, RSA UFO means: Random moduli are also called RSA UFOs (Unkown Factorisation Objects). If the definition of an RSA UFO is a modulus generated so that no one knows the factorization, this issue does obviously not exist in lattice-based cryptography, since the factorization problem is never used there. More generally, it is much ...


2

Increasing the prime numbers does not necessarily lead to an increase in security of the RSA. As an example, when the private exponent is less than $\frac{N^{\frac{1}{4}}}{3}$, Wiener's attack is able to factor $N$ in the polynomial time. There are other attacks against this system, which can be found in "Twenty Years of Attacks on the RSA Cryptosystem" and ...


2

The idea that RSA relies on the difficulty of integer factorization is called the RSA problem. The efficiency of the different methods to perform integer factorization is discussed in a similar article on Wikipedia. Theoretically, there may be more efficient methods to perform factorization; we cannot prove that there aren't. Therefore we cannot prove RSA ...


2

Since $p$ is a factor in both $N_1$ and $N_2$ you can simply calculate $p$ by using Euclid's algorithm. Once you have $p$ you can then calculate $q_1$ and $q_2$ (simply divide $N_1$ by $p$ to get $q_1$ and divide $N_2$ by $p$ to get $q_2$).


1

“Not use (only) RSA.” While RSA can be used to transport a message smaller than N (well, actually smaller than a different N that fits inside the padding aperture), the usual solution is to send data like RSA(aesKey) || IV/nonce || AES(aesKey, message) in the hybrid cryptosystem model. When dealing with toy implementations of RSA (with 7-bit keys) you ...


1

RSA works over $\mathbb{Z}_n$, therefore, you cannot encrypt and decrypt more than $n$ values. But you can choose the representatives of $\mathbb{Z}_n$ to include other values instead of the classic $\{0, 1, ..., n-1\}$. For example, if you know that you will never encrypt values smaller than $n/2$, then you can represent $\mathbb{Z}_n$ as $\{n/2, n/2+1, ....


1

You could write $E_3(64)=64^3\equiv(-2)^3\equiv(31)^3\pmod{33}$ to get the values on desired range. But this is a bad habit in terms of message encryption (and decryption). Generally the message space should be smaller than $\#\mathbb{Z}_{n}$ ( $32$ in this case ). Otherwise the encryption $E_e(x):\mathcal{P}\rightarrow \mathcal{C}$ is not bijective: ...


1

If you only care about computational complexity, it's similar: In ECC: the number of double-and-add steps is proportional to $O(|k|)$ (one double every bit, one add for each $1$ bit, in the non-windowed algorithm). Each double/add is a sequence of a constant number of field multiplications, squarings, additions and subtractions. Multiplication and squarings ...


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