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
1answer
1k 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
2k 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
549 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
147 views
+150

Algorithm for Boneh and Durfee attack on RSA

I am trying to understand various attacks on RSA and I believe that they only way to fully understand the algorithm is to implement it. I am trying to implement the code in this paper (pdf) (Private ...
6
votes
4answers
482 views

Why can’t the public key exponent in RSA be negative?

I am looking at why certain public keys in RSA can't be used, such as: 2 and all other even numbers (since $\gcd(\phi,e)$ must equal 1) 1 (since the cipher text would equal the message) 0 (since the ...
6
votes
3answers
719 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
195 views

Is there an upper bound to the private exponent in RSA?

In the RSA algorithm, we choose $p$ and $q$ as prime numbers and we select a value $e$ which is coprime to $\varphi(pq)=(p-1)(q-1)$. Then we calculate $d:=e^{-1}\bmod\varphi(pq)$. My question is: ...
6
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 ...
6
votes
3answers
6k views

In RSA, do I calculate d from e or e from d?

In the original paper introducing RSA, it is implied that one should first choose $d$ and then calulate $e$ from $p$, $q$, and $d$. However, I have found in other places (such as the wikipedia article ...
6
votes
2answers
459 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
2answers
4k views

In RSA, why is it important choosing e so that it is coprime to φ(n)?

When choosing the public exponent e, it is stressed that $e$ must be coprime to $\phi(n)$, i.e. $\gcd(\phi(n), e) = 1$. I know that a common choice is to have $e = 3$ (which requires a good padding ...
6
votes
2answers
528 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
2answers
104 views

RSA: Proving that $p+q-1 < 3 \sqrt{N}$, where N = pq and p,q are prime?

I'm doing some research into attacks on the RSA cryptosystem and have stumbled across Wiener's attack. Within the proof there exists the statement "$p+q-1 < 3\sqrt{N}$". No proof is given for ...
6
votes
1answer
285 views

RSA exhibits symmetrical properties — is it possible to form a cryptanalytic attack?

This question is broken into two sections really: Symmetry in RSA I have been analyzing raw RSA and I have noticed some interesting symmetrical properties of the algorithm. Assume that $M$ is a ...
6
votes
1answer
1k 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
3k 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
5k views

Why can’t DSA be used for encryption?

This question at StackOverflow mentions that DSA cannot be used for encrypt. But Both RSA and DSA can be used to generate public and private keys, right? (Or am I wrong?). Then why can't I use the ...
6
votes
1answer
404 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
188 views

Including a “purpose” designation in a digital signature

A signature of some data can mean many different things, such as: This is a message I sent, this is a certificate I validated,... So I was surprised that common signing schemes don't include a ...
6
votes
2answers
183 views

What is wrong in the following algorithm for computing a hash function using RSA?

I'm studying for a cryto exam and have run across this question which has stumped me. What is wrong in the following algorithm for computing a hash function? Take a message $M$, generate a random ...
6
votes
2answers
120 views

Effect of $L_n[1/4,c]$ integer factorization on RSA-2048

Using the L-notation, integer factorization of an integer $n$ has the best known complexity of $L_n[1/3,c]$ using general number field sieve. Would discovery of an algorithm with complexity ...
6
votes
1answer
2k views

how to use common modulus attack?

I am struck with the following problem: Let Alice, Bob, Chris and Eve communicate over a public network. They encrypt all messages they send using RSA system. Bob and Chris have the RSA modulus ...
6
votes
1answer
7k 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
1k views

In RSA encryption, does the value of e need to be random?

I am a novice programmer and am just finishing up an RSA encryption program that I am writing for practice. Currently I have the program generate a relatively small random value for the public key e. ...
6
votes
2answers
672 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
1answer
5k 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
513 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
1answer
217 views

RSA reconstructing private key knowing MSBs

PREMISE: This question is purely theoretical because usually an attacker will not know private exponent d and can't compare it with obtained MSB bytes. Suppose an RSA 1024 bit signature. An attacker ...
6
votes
2answers
1k 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
2k views

RSA with modulus product of many primes

I would like to ask what happens if we build an RSA system with modulus a product of more than 2 primes, for example let $n=p_{1}p_{2}...p_{L}$. I know only the classical RSA system with $n=pq$ with ...
6
votes
2answers
2k views

RSA blind signatures in practice

Hi I have a problem with moving my blind signature implementation from educational (textbook RSA) to more practical (padded RSA) side. David Chaums paper gives a following figure: $r$ - blinding ...
6
votes
1answer
379 views

What does “a 15360-bit RSA key is the equivalent to a 256-bit symmetric key” mean?

NIST key management guidelines suggest that 15360-bit RSA keys are equivalent in strength to 256-bit symmetric keys. If a 15360-bit RSA key is the equivalent to a 256-bit symmetric key, does that mean ...
6
votes
1answer
732 views

What signature schemes allow recovering the public key from a signature?

It seems to be possible to retrieve the (public) key used for creating an ECDSA signature just from the signature alone. This seems like an interesting property; as far as I know, RSA doesn't share ...
6
votes
1answer
1k views

CKM_RSA_PKCS vs CKM_RSA_X_509 mechanisms in PKCS#11

What is the exact difference between the CKM_RSA_PKCS and CKM_RSA_X_509 mechanisms in the PKCS#11 v2.20 specification (Please ...
6
votes
1answer
3k views

RSA-PSS salt size

One of the inputs of RSA-PSS signing and verification is the salt size. According to PKCS#1, you must know the salt size before the verfication is carried out. However, this makes interoperability ...
6
votes
2answers
564 views

State of the art RSA key generation

I would like to know if there is an algorithm to generate a RSA key at the state of the art of the present cryptanalysis. Beside the key lenght I know there are some weakness in the choice of prime ...
6
votes
3answers
659 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
2k 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
2k 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
663 views

Proof that padded RSA is CPA-secure

I'm referring to page 383 of J. Katz and Y. Lindell's Introduction to Modern Cryptography. The book presents a padded RSA: ${\bf Key Generation:}$ same as Textbook RSA (given security parameter ...
6
votes
1answer
622 views

What is the harm if I publish an encrypted RSA private key publicly?

What is the harm if I publish an encrypted RSA private key publicly? Or in this case, what is the harm if I publish many thousands or millions of them? Assuming that the private key is encrypted ...
6
votes
1answer
521 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
535 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
715 views

Is it possible to reduce the size of an RSA key?

The details about what an RSA key is made up of are explained succinctly here. Is it possible to reduce the amount of data that's usually packaged with the (private) key and then derive it later?
5
votes
4answers
820 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
731 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
846 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
3answers
2k views

How to perform authentication without central server in P2P?

How can one be sure that the man who you're talking with is the one who you think he is? i.e. How can one perform authentication in P2P network without a central trust server or Certificate Authority? ...
5
votes
2answers
1k views

Is RSA key size the size of private key exponent?

I have implemented a key pair generation scheme for RSA algorithm. I have taken the length of private key exponent as RSA key size, but then I've got to know that RSA key size is the size of the ...
5
votes
2answers
740 views

Is RSA encryption of a cryptographic hash with a private key the same as signature generation?

It is often said that RSA encryption with a private key is the same as signing (signature generation). Will RSA encryption with a private key over a cryptographic hash give the same result as ...