# Tag Info

## Hot answers tagged rsa

7

How is it possible to memorize or remember a key that is about 4000 bits long? One could reasonably ask the same question about AES: how is it possible to remember a key that is 128 bits long? The answer is: "it doesn't really matter, because no one actually tries to remember a sequence of 128 random bits, much less 4000 bits anyways". Instead, we ...

6

No, it's not possible to recover the private RSA key; not with a timing attack, not with a debugger, not with any technical means. There isn't enough information on the victim's computer. The timing attack you describe requires timing the decryption operation, which could reveal the decryption key. But the malware isn't ever decrypting anything, it's just ...

5

A 4000-bit RSA key is reasonable (more precisely, that would be the bit size of the public modulus; and 4096-bit would be more common). But it is not reasonable to memorize it (or, more precisely, that the owner try to memorize the corresponding private key); and that's practically never done. One does not ask normal users to memorize or remember a key, or ...

4

I think you don't quite understand how RSA signatures work (and why they are the size they are). When generating an RSA signature, we follow a two-step process: We take that hash of the message we're signing, and convert (and pad) it into an integer $M$ which is between 0 and $N$ (where $N$ is a large integer that specified by the RSA key) We use the RSA ...

4

You should be able to use D for any c by blinding the query to D. Repeatedly try r:=uniformly random in 1..n-1 $x:=D(c\cdot r^e\bmod n, e, n)$ $m:=x\cdot r^{-1}\bmod n$ $c\cdot r^e$ is uniform in the range 1..n-1 (with the possible exception of when c is a multiple of a factor of n, which I haven't checked), so no matter which 1% of c values it is that D ...

4

Since it sounds a lot like homework, I will only give a hint, not the actual answer. First, you don't want to mess with $e$, since you can not be sure that a different $e$ is actually a valid exponent ($e$ has to be coprime to $\phi(n)$, which contains at least $2$ as prime factor). RSA is not IND-CCA. The same attack that works against IND-CCA also works ...

4

I had a similar problem, and it took me a long time to figure out all the math, as some of the proofs can be rather terse. So, I took it upon myself to write a full explanation of how to factor N, without all the symbols and relying on a bit less prior knowledge. Anyway, such a system is not safe. If you know a valid $e$ and $d$, you can factor $N$. ...

4

If I right understood your question, you think that from N it is easy to compute $p$ and $q$. But it is not true. For computing $p$ and $q$ from $N$, you need to solve factorization problem. And this is very difficult. If $N$ small number, then you can use brute force. But when it comes to RSA, $N$ is a very big number. And it will take many hundreds years ...

3

There's an easy attack against public keys with $e=3$. Here's how it works; the attacker selects an arbitrary message $M$ that hashes to an odd value $H$ (or, more generally, a $H$ of the form $k8^n$ for odd $k$). Since half of the potential messages hash this way, this is not a severe limitation to the attacker. Then, the attacker looks for a perfect ...

3

We do initially did not have the specification of prv_key_enc, thus we can could not answer with some level of certainty anything more than: the maximum size of its output, in bytes, is at least 128. Looks like the answer now is: the output is always exactly 128 bytes before Base64 encoding, making it exactly 172 bytes. On thing is sure: the term ...

3

If you knew $pq$ and $p+q$, you could find $p$ and $q$ by algebra. If you knew $pq$ and $(p-1)(q-1)$, you could find $p+q$. Now $e_1d_1-1$ and $e_2d_2-1$ are both said to be multiples of $\phi(n)$, so their greatest common divisor should be a (smaller) multiple of $\phi(n)$, from which you could easily guess $\phi(n)$. I've probably said too much already, ...

2

I happened to see some similar question like this. The question mentioned about sending fake signature message. The method is like this: Find some random string R. Use the public key to encrypt the random string R, let the result be X. (R,X) is your signature pair.(Think backwards) When someone verifies the signature, he'll compare {R} with X which are ...

2

By key I assume you mean a passphrase. 4000 bits is 500 letters, with an average letter count of 4.5 in an English word, that's 125 words. With 15-20 words per sentence that's anywhere from 5 to 8 paragraphs. A small poem. Yes, it's practical. An actual key (like the PGP key one would post on their website) is ideally random so you can't be expected to ...

2

First off, the maximum size of a message you can use is determined by the desired length of the padding (in my case, I am using RSA-2048 so I wanted a final padded length of 256 bytes) and the hash function you are using. The formula is messageLength = desiredLength - 2 * hashOutputSize - 1 (in my case, I wanted to use SHA-256 so hashOutputSize would be 32 ...

2

If you know even a single key pair $(e,d)$, then you can factor $N$, so that's pretty much the ultimate attack — efficient, total key recovery. For a short, digestible proof of this, see the last fact on page three of Dan Boneh's Twenty Years of Attacks on the RSA Cryptosystem.

1

The RSA encryption function $f(m)_{(e,n)}:=m^e \mod n$ is a function that maps inputs from ${\mathbb Z}_n$ to outputs of ${\mathbb Z}_n$, where ${\mathbb Z}_n=\{0,\ldots,n-1\}$. Consequently, your output is always an integer in ${\mathbb Z}_n$ and if you use RSA with a 1024 bit modulus $n$, then your output (ciphertext) will be 128 bytes. Edit: After ...

1

What you describe is a digital signature, which works using methods very similar to the one you suggest. Examples include elgamal-signature and RSA signature schemes (the second of which I would recommend you read). Digital signatures allow you to provide a public signature that 'proves' you provided the message. As the author, you would produce database ...

1

While there are some obvious checks you can do, you can't cover everything: You can check that the modulus is a composite odd number of the appropriate size If you want to put in the effort, you can do a quick check if the modulus has any small factors You can check if the public exponent is an odd number > 1 However, you can't check beyond that; you ...

1

I am not sure if I understand your requirement correctly, but from the first part of your description I think you want the following (I skipped the second part since I do not understand the meaning of "$+$") : Set up a public key $pk$ which can be used to encrypt a message $m$ and you want to split the corresponding private key $sk$ into two shares $sk_1$ ...

1

RSA has quite a few aspects, which are utilized implicitly, and these questions aim at those: Concerning your first point about what happens if $x$ is not coprime to $n$, it does not compromise the correctness of the encryption and decryption, but if you find such an $x$, you also found a nontrivial factor of $n$. However, if $p$ and $q$ are prime, the ...

1

Firstly, I assume we are talking about classical computers Implementing a brute force attack on a RSA may not be the most sensible thing, unless of course the security parameter of your target system is small.. (160 bit numbers! ) Even then you may not want to implement a brute force here.. try using Fermat's Factoring or Pollards $\rho$ method. If you ...

1

There are indeed multi-prime instances of RSA (ftp://ftp.rsa.com/pub/pkcs/pkcs-1/pkcs-1v2-0a1d1.doc‎). Regarding their security, I would suggest you to have a look at (cacr.uwaterloo.ca/techreports/2006/cacr2006-16.pdf‎) and have a look at this previous thread.

1

In fact in one of the RSA Labs CryptoBytes magazines, multiprime RSA versions and their applications for certain scenarios were discussed. Unfortunately i don't have a link to this article [possibly by Boneh] but a google search under multiprime RSA unearths quite a few links and technical papers.

1

The product can be of more than 2 prime numbers, but that makes it easier to break. Whatever method that is being used to try to break your encryption (for example elliptic curves) will have another number that factors into your modulus and that makes a correct hit more likely. After that, the modulus gets reduced to a simpler problem. This security ...

1

There's a much simpler way to factor $n$ when you know $d$ at least when $e$ is small (like when it is usually 65537). You know that $ed = 1 \, (\textrm{mod} \,\phi)$. Since you know $e$ and $d$ you can calculate $S = ed - 1$ and this number must be divisible by $\phi$ due to the first equation. Note that the magnitiude of this value is around 65537 times ...

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