Tag Info

Hot answers tagged

19

Actually, if you're willing to consider a somewhat larger $e$, I found a solution that makes the decryption part real cheap. This solution has $e = 446185741$ and $n = ...


9

An option strictly matching the question's statement (which requires $e=65537$) is to choose the public modulus $n$ as the product of many small primes $p_i$, perhaps $k=64$ primes of $32$ bits. That's multiprime RSA pushed to the max. The potential speedup is considerable. For small $k$, and standard arithmetic (quadratic multiplication and modular ...


6

The statement a 15360-bit RSA key is the equivalent to a 256-bit symmetric key does not take into account quantum algorithms. In fact, it is based on a specific computation model. It is just based on the fact that there exist sub-exponential algorithms for factoring and therefore you need longer keys than when using symmetric-key crypto where it is ...


5

The prime number theorem says that there are approximately $N/\log{N}$ primes less than $N$. If we consider $2048$ bit RSA, that means the primes we are using are $1024$ bits. How many $1024$ bit prime numbers are there? Approximately $2^{1025}/\log{2^{1025}} = 2^{1025}/1025\approx 2^{1015}$ (from the theorem). So, just to store the primes we are going to ...


5

With pure asymmetric encryption there is no way to ensure integrity and authenticity, since anyone who knows your public key can encrypt any message for you. For that you would need either a symmetric key to use for a MAC (in which case you could use it/derivatives for symmetric encryption too) or a signature from the sender. And in the latter case the ...


4

No, if the RSA cryptosystem is secure, i.e. when it uses random padding such as PKCS#1 v1.5 padding or OAEP, then you cannot. As Stephen already mused, it is pretty likely that you can find out the key simply because it is included or can be derived; generally public keys are not meant to be secure. If textbook (raw modular exponentiation) RSA is used then ...


4

No, we do not know an algorithm running in linear time (or even polynomial time, relative to the number of digits in $n$) that outputs 'true' if $n$ is the product of exactly two prime numbers, and 'false' otherwise. If such an algorithm existed, I do not see that it would imply possibility to factor $n$, or otherwise break RSA. For sure, it would not be a ...


3

You can't get a man-in-the-middle (MitM) resistant channel out of a vacuum. You need some common knowledge beforehand. Luckily all one needs is a shared trust relation. Suppose the server Steve trusts Carol, suppose further the client Charlie trusts Carol aswell. As an example I'll give a simplified TLS-RSA key exchange because it's particularly easy. ...


3

If you are using a secure signature algorithm, padding and all, then it must be secure for messages of any length. So in that sense you are good. However, in many protocols your messages must include something to prevent replay attacks, like an incrementing counter, in which case you shouldn't be signing just a single number if the messages are meant to say ...


2

Let's try to simplify and abstract your protocol a bit. Instead of your server and client, we just have two parties, let's call them Sally and Charlie. Charlie has a key pair $K = (K_i, K_u)$ for a suitable asymmetric cryptosystem $\mathcal E$. We assume that this cryptosystem is partially homomorphic, such that $\mathcal E_K(a) \otimes \mathcal E_K(b) = ...


2

Both the AES key size and the RSA key size matter, because it's no use adding security beyond the weakest link. Here the weakest link is 2048-bit RSA, which is considered roughly equivalent in security to 100-128-bit symmetric keys (depending on who you ask). So having a password with much more than 100 bits of entropy would be fairly useless. In practice, ...


2

Some information about the RSA public key is revealed by the ciphertext. This is due to the fact that the ciphertext is a value between 1 and the modulus. Beyond this, I don't know what is revealed. However, what I can prove is that whatever you can learn from the plaintext and ciphertext together, you can learn from the ciphertext only. I can prove this ...


2

I further assume you mean a DER-encoded unencrypted PKCS#8 RSA key, since you wouldn't care about exposing an encrypted key, and it's a conventional two-prime key with equal-size factors (each 1024 bits) and the ubiquitous e=65537 using the standard PKCS#1 CRT-form representation. I also note that 21 bits is a really odd amount to disclose: not 2 octets, ...


2

The ciphertext should look like a random element within 1 and the modulus (since it is a value from within that range as Yehuda Lindell pointed out). Without knowing the modulus it should not be feasible to distinguish two ciphertexts encrypted with different keys. If the public key is stored in some key-database you could ofc try to encrypt the decrypted ...


2

Yes, and it's devastatingly effective, too. See OAEP and other RSA/asymmetric-function padding standards. OAEP is what you should use these days so far as I am aware. PKCS#1 has other defined padding schemes also (eg PSS, PKCS1.5), only some of which are effective.


2

If you were using $e=3$, then there is a well known attack by Bleichenbacher that enables the trivial generation of a signature that passes verification. This attack was never published, but is described here. Note that this attack appeared in a real vulnerability in Kindle (and some versions of Android). In any case, the attack does not work for $e=65536$. ...


1

Your idea seems secure, but it is more complicated than it needs to be. If you only need to know if the "secure information" in the document matches some public information (stored on an insecure computer), it is enough to calculate a preimage resistant hash of the document (e.g. SHA-256). The document needs only to be unguessable, like a 256-bit random ...


1

I'm quickly assuming your question asks how to retrieve the public (RSA-) key from a set of samples of unencrypted and encrypted messages. If you're question is about: "How can I get my files back after being infected by CryptoWall?" I suggest you read the hits by the search function on InfoSec. Please also note that in most use cases RSA isn't used to ...


1

Let's assume that the leaked bits were from the "actual" private key, i.e. the primes $p$, $q$, the private exponent or its value modulo one of the primes. A Coding-Theoretic Approach to Recovering Noisy RSA Keys gives a bound of 20% of the key material needing to be known for an attack. Given that you have a 2048-bit key, I don't think leaking 21 bits ...


1

They are both the same size, however they were created at different times during the factoring challenge, which is why one uses the bit size and the other uses the decimal size. They are created from different primes and are not directly related to eachother other than the fact they are both from the chllenge. The first series of numbers in the challenge ...


1

The multiplicative group $Z_m$ of integers modulo $m$ has exactly $\phi(m)$ elements by definition. Thus for any element $a$ of $Z_m$ the equation $$ a^{\phi(m)}=1~(mod~m) $$ holds, where $1$ is the multiplicative identity of $Z_m$ (the residue class $km+1$ of all integers congruent to 1 modulo $m$). In RSA, $e$ and $d$ are indeed inverses modulo ...



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