an asymmetric (e.g. public-key) cryptosystem, based on modular exponentiation with big exponents and modulus. RSA can be used both for signature and encryption.

learn more… | top users | synonyms

7
votes
3answers
3k views

What are some disadvantages of homomorphic encryption schemes?

I'm doing some self-teaching / research for my own benefit in homomorphic cryptography. I've studied both additive and multiplicative schemes (Pallier and RSA respectively), but all I can seem to ...
7
votes
2answers
1k views

Cycle attack on RSA

I originally posted this question in the mathematics section, you can see it here. Let $p$ and $q$ be large primes, $n=pq$ and $e : 0<e<\phi(n), \space gcd(e, \phi(n))=1$ the public encyption ...
7
votes
2answers
263 views

RSA: Letting $p$ and $q$ have different bit-size

I am aware that there are concerns if $p$ and $q$ are close i.e. $\Delta=|p-q|$ can't be too small. But I would like to know if there are any known attacks for cases where $p$ and $q$ take on ...
7
votes
3answers
1k views

Would the ability to efficiently find Discrete Logs have any impact on the security of RSA?

This answer makes the claim that the Discrete Log problem and RSA are independent from a security perspective. RSA labs makes a similar statement: The discrete logarithm problem bears the same ...
7
votes
4answers
544 views

How to argue to a paranoid that RSA is safe?

From today's standpoint, most people would claim RSA to be secure. However, to my knowledge, this is purely based on the speculation that no one knows a computational feasible way to find a $d$ for ...
7
votes
2answers
486 views

Given a message and signature, find a public key that makes the signature valid

Given a message $M$ and a signature $S$, is it feasible to find a RSA public key $(n,e)$ such that $S$ verifies as a valid signature on $M$ (using this public key)? What if we're given one public key ...
7
votes
1answer
373 views

Exposing RSA private-key data… bad?

We know that exposing $p$, or $q$ or $\phi(n)$ results in trivial attacks on RSA since they allow us to factor $n$ and to compute the private exponent $d$. In OpenSSL (and most RSA implementations) ...
7
votes
2answers
595 views

How does Clifford Cocks 'Non-Secret Encryption' work?

I have read Clifford Cocks "A Note on 'Non-secret Encryption'" and thought I would try to implement this, but I don't seem to be able to get it to work. I'm obviously missing something. From the ...
7
votes
4answers
537 views

Is an RSA variant with public exponent $e=f+(p-1)\cdot(q-1)$ safe (for $f$ random in some small interval)?

Alice is going to use some existing RSA scheme (employing industry-standard signature or/and encryption with proper padding), which she can't change, or influence beyond her choice of key. In this ...
7
votes
2answers
3k views

What are advantages of using a HMAC over RSA with SHA-1 hashes?

I am currently studying for an exam and this was a previous question: Give one advantage of using HMACs over using RSA to sign SHA-1 hashes. My thoughts are that it has something to do with the ...
7
votes
1answer
3k views

How do other, non-RSA algorithms, compare to the PKCS #1 standard?

Arguably the PKCS suite of standards have a profit-oriented bias as they are promoted by RSA and promote their algorithms over others in the form of RFCs and other means. I'm considering the ...
7
votes
2answers
1k views

How to better generate large primes: sieving and then random picking or random picking and then checking?

I'm writing an RSA algorithm, and am wondering what is the best and/or usual way to choose the initial prime numbers (p and q). I know of two methods to achieve this, one based on a prime number ...
7
votes
2answers
1k views

Using the same RSA keypair to sign and encrypt

The RSA signature operation is basically the same as encrypting with the private key. In particular, both operations use the same kind of keys. Is it safe to use the same RSA keypair both for ...
7
votes
2answers
2k views

RSA and prime difference

It is known that the two prime factors $p$ and $q$ of an RSA modulus $n$ should not be too close to each other, otherwise an attacker may factor the modulus. In other words, $\Delta = \left| p - q ...
7
votes
1answer
190 views

In RSA, rationale for prime $p$ with $p-1$ having prime factor $u$ with $u-1$ having large prime factor?

In the 1978 RSA paper, it is recommended, among other things, to choose primes $p$ such that $(p-1)$ has a large prime factor $u$. This was motivated by Pollard's p-1 algorithm. Further, the authors ...
7
votes
1answer
484 views

What is the history of recommended RSA key sizes?

One can find up to date recommended key sizes for RSA at http://csrc.nist.gov/publications/nistpubs/800-131A/sp800-131A.pdf for example. In short it suggests a key size of at least 2048 bits. Is it ...
7
votes
1answer
992 views

RSA-OAEP Input Parameters

When creating padding for RSA using OAEP, a message is prepared as follows: Hash(Input Parameter) || Zeros || 1 || Message My question is, what should the Input ...
7
votes
1answer
1k views

How can I determine the GPG/PGP key ID from the RSA modulus?

According to http://www.pgp.net/pgpnet/pgp-faq/pgp-faq-keys.html#key-public-key-forgery, key ID is some lower bits sequence from the modulus (i.e. the $n$ variable): A PGP key ID is just the ...
7
votes
1answer
418 views

Is SSH public key authentication weakened by 'none' cipher?

As far as I know, SSH2 first does a key exchange based on the server host key and brings up transport authentication and encryption derived from this kex. The real authentication (password or public ...
7
votes
0answers
330 views

Security of RSA for paranoids with padding?

RSA for Paranoids (RSAP) (in cryptobytes v3n1), also known as Unbalanced RSA, is a variant of RSA proposed in 1995 by Adi Shamir, as a mean to increase the RSA public modulus size while keeping ...
7
votes
0answers
884 views

Bleichenbacher 1998 “Million message attack” on RSA

I have been reading Bleichenbacher's 1998 paper on a forged message attack on RSA. The paper assumes access to an Oracle that takes a ciphertext $c$ and will check the decrypted text for valid PKCS #1 ...
6
votes
4answers
3k views

Why is it important that phi(n) is kept a secret, in RSA?

Why is it important that $\phi(n)$ is kept a secret, in RSA?
6
votes
3answers
625 views

Initialize a PRNG with a password

Let's assume that we have a secure PRNG. Is it "safe" to initialize it with password, or seed based on a password like SHA256(password)? If yes, is it "safe" to generate an RSA or DSA key from it? ...
6
votes
3answers
2k views

Is sharing the modulus for multiple RSA key pairs secure?

In the public-key system RSA scheme, each user holds beyond a public modulus $m$ a public exponent, $e$, and a private exponent, $d$. Suppose that Bob's private exponent is learned by other users. ...
6
votes
2answers
7k views

How much computing resource is required to brute-force RSA?

It's been over 30 years since Rivest, Shamir and Adleman first publicly described their algorithm for public-key cryptography; and the intelligence community is thought to have known about it for ...
6
votes
3answers
1k views

Why is the complexity of RSA-1024 80 bit and not 86 bit?

Why is the complexity of RSA-1024 80 bit and not 86.76611925028119 bit? Here is the complexity for the GNFS (pulled from the linked Wikipedia article): $$\exp\left( ...
6
votes
2answers
370 views

Is encrypting credit card numbers one by one with rsautl secure?

I wish to encrypt credit card numbers one by one using asymmetric encryption on the command line. My current approach is this… Encrypt: ...
6
votes
1answer
7k views

Chinese Remainder Theorem and RSA

Wikipedia has a nice section regarding the speedup of the RSA decryption using the Chinese Remainder Theorem here. I need to understand the implementation of a similar speedup for the encryption ...
6
votes
2answers
460 views

What is the key strength reduction encrypting only 160 bits of data using RSA1024 for signatures?

I am attempting to determine the strength of an incorrectly implemented 1024 bit RSA signature scheme. The weakness in the implementation is that the padding data lacks random numbers. As a result, ...
6
votes
1answer
852 views

Why Elliptic curve cryptography are not popular in practice

RSA and ElGamal can be implemented using the technique of Elliptic curves. I am confused on why the it seems that Elliptic curves are not so popular in cryptographic applications since they provide ...
6
votes
1answer
319 views

Anonymous trust/reputation system

Suppose there are 3 persons, Alice, Bob and Peter. They are identified by their pseudonyms (public RSA keys). Alice has a key Alice, Bob has ...
6
votes
1answer
2k views

Is a known plaintext, ciphertext, and public-key a viable attack on RSA?

Assume Alice and Bob are using RSA to create a common session key and Cindy is listening, attempting to obtain the session key. Alice and Bob each have their public- and private-key pairs ...
6
votes
2answers
450 views

RSA Signature Weak Padding Attack

Assume that we have a message $m$ of size $n$, and it is padded with two 01 bytes in front. Then the signature $s$ is computed using a private key $ks$. Can we ...
6
votes
2answers
6k views

How does a chosen plaintext attack on RSA work?

How can one run a chosen plaintext attack on RSA? If I can send some plaintexts and get the ciphertexts, how can I find a relation between them which helps me to crack another ciphertext?
6
votes
1answer
4k views

Why has the RSA factoring challenge been withdrawn?

Wikipedia states that RSA challenge has been withdrawn. Does it mean that an efficient factoring algorithm is "just around the corner"? or are there some other reasons? If the challenge was still ...
6
votes
1answer
456 views

Would RSA-encrypting a private key for itself constitute a vulnerability?

I'm planning to encrypt some individual files for storage, using the GnuPG implementation of RSA. If I happened to encrypt the private key corresponding to the public key used for encrypting -- either ...
6
votes
2answers
411 views

Is perfect-forward secrecy achieved with RSA?

I am new to cryptography and am going through the book Understanding Cryptography by Paar and Pelzl. From what I understand Symmetric key distribution systems like Kerberos do not provide PFS ...
6
votes
1answer
4k views

How much stronger is RSA-2048 compared to RSA-1024?

How much stronger is RSA-2048 compared to RSA-1024? It is hard to imagine very big numbers. So what would be your way to explain the difference to someone who doesn't know much about cryptography?
6
votes
1answer
339 views

What does “Inverting the RSA function is as hard as factoring” mean (a rigorous explanation or intuitive will do)?

I was reading that a current open problem is if inverting the RSA function is as hard as factoring. Does this mean that, its an open problem whether, if given a subroutine that computes in ...
6
votes
2answers
1k views

How much can we compress RSA public keys?

I am wondering to what degree we can define an RSA variant, with a security argument that it is as safe as regular RSA with a given modulus size $m$ (e.g. $m=2048$), in which the public key has a ...
6
votes
1answer
264 views

Blinding twice in RSA

I understand that if you have a message $m$, you can blind it by selecting a random $r$ and then multiplying $r^e\times m \pmod{n}$ Someone else then signs it with $d$, raising to the power of $d$: ...
6
votes
3answers
613 views

Security equivalence proofs for breaking RSA

It is my understanding that while a practical solution to the factoring problem will definitely break RSA, it has never been proven that the security of RSA is equivalent to factoring. In otherwords, ...
6
votes
2answers
1k views

RSA-based authentication and key-agreement protocol

An authentication and key-agreement protocol between devices shall mutually demonstrate their identity, and establish a shared random secret $R$ suitable for securing later communications. To that ...
6
votes
1answer
1k views

Is a private RSA key vulnerable to a chosen plaintext encrypted with that private key?

I grasp that having known plaintext encrypted with the public key doesn't provide a means of discovering the private key (that being the whole point...). But if one were in a situation where they ...
6
votes
1answer
430 views

Prove that textbook RSA is susceptible to a chosen ciphertext attack

Given a ciphertext $y$, describe how to choose a ciphertext $\hat{y} \neq y$, such that knowledge of the plaintext $\hat{x}=d_K(\hat{y})$ allows $x=d_k(y)$ to be computed. So I use the fact that the ...
6
votes
1answer
386 views

Threshold Signatures for RSA and DSA

I have a few questions relating to threshold signatures: a scheme where $n$ participants hold a key share and any $t$ of them can conduct a protocol using their shares that results in a valid RSA or ...
5
votes
3answers
651 views

RSA with modulus n=p²q

I've been wondering what would happen if the RSA modulus would be $n=p^2q$ instead of $n=pq$. I feel like there is an obvious security flaw (as there is with most modifications). Would this choise of ...
5
votes
2answers
639 views

uniqueness of the RSA public modulus

What is the probability that two separate RSA public moduli are the same? For example, consider a 2048-bit modulus. The number seems to be huge, but the choice for prime factors p and q is much more ...
5
votes
4answers
703 views

Subverting the key generation step in RSA public key cryptography

I am interested in the ways the implementation of an RSA key generation implementation can or cannot be subverted so that the subverter has an advantage, but the owner of the key, and the people who ...
5
votes
3answers
2k views

Why should the RSA private exponent have the same size as the modulus?

Consider the generation of an RSA key pair with a given modulus size $n$ and a known, small public exponent $e$ (typically $e = 3$ or $e = 65537$). A common method is to generate two random primes ...