New answers tagged

0

New systems should not use RSA unless interoperability requires it. See for example this twitter thread for current zeitgeist: https://twitter.com/veorq/status/1148258833896263680 With RSA, the recommendation is to not even have a mode where data is encrypted using RSA directly, even if it fits. Always use hybrid encryption to not have two code paths. The ...


0

That should be secure for the time being. I'd max out the RSA key size if I were you (future proofing) as 2048 will not survive quantum computers (neither will 4096 in the long run, but it gives you more time) AND because the bigger the RSA key size the more data you can encrypt. Remember that the max data you encrypt with RSA is your key size minus ...


0

OK posting my own answer, not sure if this is correct, but: The RSA accumulator scheme relies on the lack of knowledge of the totient function, which is used for computing inverse powers. The EC scheme doesn't have this restriction so you're able to prove any value is a member of the set simply by computing its inverse.


2

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


0

I had the same question and so I landed here. RSA has two key properties The mapping $m \to m^e (mod\ N)$ is a bijection The inverse mapping $(m^e)^d \equiv m\ (mod\ N) $ is easy to compute (given $p$ and $q$ of course) From what I read, the proof of working (of these two properties of RSA) assumes that $p$ and $q$ primes. So I worked on a few examples ...


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


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


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


0

Question/answer one by one: AWS access key ID is a form of unique user/account identifier Correct, AWS access key is a unique identifier for a user. BTW, in some cases, it could be considered as sensitive data, sharing access key can lead to tracking like who accesses which systems and when, check this post for more details. If you are an ...


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


0

Specialized hardware is the answer. This machine uses asynchronous computation, very likely using parallel Montgomery multipliers and a local register of 4096 bits (4096 seems to be the largest key size for RSA, so we can conclude that this is the size of the register). Similar hardware can be found in Smart Card CPU's. These don't go as fast, because they ...


0

Update (26.06.2019), this was actually done in February 2012. Paper: Ron was wrong, Whit is right They collected 11.4 Million public RSA keys, where almost 27000 of them are vulnerable. These include 10 2048-bit RSA keys. It was possible by applying a special form of the GCD algorithm. They suspect that the main cause for this to happen is that proper ...


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


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


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


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

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


Top 50 recent answers are included