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.
6
votes
3answers
358 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, ...
3
votes
2answers
288 views
Can RSA encryption produce collisions?
In RSA, a message is encrypted by $m^e \pmod N$. $N$ is the modulus, $m$ is the message and $e$ is the public exponent. (I know that $m$ should not be greater than $N$.)
My question is, can $m^e$ be ...
5
votes
2answers
737 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 ...
1
vote
2answers
175 views
One-way function and factoring
I am confused about the hardness of the one-way function behind cryptography -- if someone could factor the large number produced back into two primes quickly then the one-way function would be ...
2
votes
2answers
2k 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?
4
votes
1answer
114 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 ...
1
vote
2answers
216 views
My custom handshake
I am a beginner in cryptography and I designed a custom handshake between 2 entities $\rm C$ (client) and $\rm S$ (server) which should meet the following requirements:
Requirements:
The handshake ...
1
vote
3answers
301 views
RSA finding the inverse of the public exponent
I have a very basic doubt in RSA key generation and its usage.
In RSA key generation you choose two large prime numbers of a very large order. Then you multiply them.(eq $p \cdot q = N$) Now, ...
1
vote
1answer
136 views
How are the primes used to generate RSA keys?
I am confused about how keys in RSA asymmetric encryption are generated and what the implications for open communications are. Textbooks say the one-way function is merely two primes (with some ...
5
votes
3answers
427 views
Is RSA padding needed for single recipient, one-time, unique random message?
I want a way to encrypt files using this process: http://crypto.stackexchange.com/a/15 . That is: generate a random password, use that to AES-encrypt a file, and use an RSA public key to encrypt the ...
3
votes
3answers
4k views
RSA encryption with private key and decryption with a public key
Does the encryption with a private key and decryption with a public key works in RSA? Is it done when we use RSA for sender authentication ?
Thanks.
4
votes
1answer
185 views
Why does RSA give better security on longer messages?
I am trying to understand the notion of RSA security.
Choosing a public exponent where $e = 3$ facilitates the calculations, considering that it is secure if the plaintext or message is long.
If the ...
5
votes
1answer
358 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 ...
3
votes
2answers
1k views
Difference between “Signature Algorithm” and “Signature Hash Algorithm” in X.509
What's the difference between the "Signature Algorithm" and the "Signature Hash Algorithm" found in an X.509 certificate? Why does it need a "Signature Hash Algorithm"?
Edit:
I'm creating the ...
2
votes
1answer
125 views
RSA-OAEP versus RSA with Fujisaki-Okamoto construction
I was wondering why the Fujisaki-Okamoto construction (or one of its variants) is not (at least commonly) used with RSA to achieve CCA2 security? Does anyone know of any speed comparisons between RSA ...
4
votes
2answers
203 views
X.509 CSR: Why does CA remove signature?
I just read this article on Wikipedia: Certificate Signing Request
I'm not a PKI or Crypto expert. As I understand, a CSR (certification request) is always signed by the PKCS#10-Request creator.
...
4
votes
0answers
78 views
RSA security assumptions - does breaking the DLP also break RSA? [duplicate]
Possible Duplicate:
Would the ability to efficiently find Discrete Logs have any impact on the security of RSA?
I'm wondering if breaking the DLP, that is the basis for ElGamal and DSA, ...
16
votes
3answers
1k views
How big an RSA key is considered secure today?
I think 1024 bit RSA keys were considered secure ~5 years ago, but I assume that's not true anymore. Can 2048 or 4096 keys still be relied upon, or have we gained too much computing power in the ...
17
votes
2answers
823 views
How are primes generated for RSA?
As I understand it, the RSA algorithm is based on finding two large primes (p and q) and multiplying them. The security aspect is based on the fact that it's difficult to factor it back into p and q. ...
2
votes
1answer
111 views
Signing a GCM MAC
If I encrypt a message with AES-GCM, is it safe to use the MAC as the hash in a DSA/RSA signature? That is, if someone knows the AES key and nonce, will they be able to generate a different message ...
6
votes
1answer
300 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) ...
1
vote
1answer
98 views
Proof of batch RSA security
Suppose we have two encrypted messages with two different public key issued from the one server. There is a client who wants to send these to messages to the server.
In the middle there is an ...
4
votes
1answer
199 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 ...
4
votes
1answer
181 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 ...
4
votes
1answer
461 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 ...
6
votes
2answers
269 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, ...
4
votes
2answers
297 views
Does RSA padding have to be unpredictable if the payload is?
I'm trying to understand the precise requirements on padding when using RSA for encryption.
Suppose Alice uses RSA to encrypt a payload $M$ that cannot be guessed (say, a random nonce): Alice send ...
2
votes
1answer
409 views
Is RSA of a random nonce with no padding safe?
Consider the following protocol: Bob has a private RSA key $B_{priv}$, and Alice knows the public key $B_{pub}$. Alice wants to send confidential messages to Bob (no integrity intended). To send a ...
6
votes
3answers
1k views
Why RSA encryption key is based on modulo(phi(n)) rather than modulo n
While calculating RSA encryption key we take modulo(phi(n)) rather that modulo(n). I couldn't understand why its so?
3
votes
3answers
302 views
How can I avoid calculating with huge numbers when implementing the RSA algorithm
There is 26-letter English alphabet.
There is the plain text: TRYAGAINLATER.
I need to encrypt it by RSA algorithm with the public key 53.
What is the ciphertext?
...
6
votes
1answer
638 views
Why does the PKCS1 RSA private key structure contain more than just exponent and modulus?
The ASN.1 spec for the PKCS1 RSA private key format is as follows:
...
1
vote
1answer
2k views
Calculating private keys in the RSA cryptosystem
The number $43733$ was chosen as base for an implementation of the RSA system.
$M=19985$ is the message, that was encrypted with help of a public key $K=53$.
What is the plaintext text?
What is the ...
2
votes
2answers
266 views
Is it possible to figure out the public key from encrypted text?
Suppose Alice sends messages to Bob by encrypting the messages with Bob's public key.
Eve knows that the data is encrypted using RSA, but does not know the public key. Can Eve figure out the public ...
6
votes
2answers
539 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 ...
3
votes
2answers
3k views
When to use RSA and when ElGamal asymmetric encryption
If i am not wrong in cryptography there are 2 basic cryptographic schemes for public key cryptography. RSA encryption whose security is based on the infeasibility of solving the factoring of big ...
1
vote
0answers
76 views
Two untrusted party want to exchange data: how to ensure each one gets the data it needs? [duplicate]
Possible Duplicate:
Two untrusted party want to exchange data: how to insure each one gets the data it needs?
I am trying to come up with what could maybe be a novel algorithm for an ...
2
votes
1answer
528 views
RSA cracking: The same message is sent to two different people problem
Suppose we have two people: Smith and Jones.
Smith public key is e=9, n=179 and Jones public key is e=13, n=179.
Bob sends to ...
5
votes
3answers
590 views
Is it possible to validate a Public Key in RSA?
If I have a 1024-bit number, and someone is telling me that it is in fact a valid RSA public key, is there any way I can quickly validate that it is indeed so (without cracking RSA)?
(I suppose I am ...
1
vote
3answers
209 views
two public keys with same passphrase insecure? | can two hashes be compared?
Suppose someone had generated a 2.048-Bit RSA GPG/PGP key pair and published the public key on the usual key servers. Then he withdraws this key and generates a new one in 4.096-Bit RSA using the same ...
5
votes
2answers
546 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 ...
5
votes
1answer
113 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 ...
3
votes
1answer
589 views
RSA: If n=35, show that e will equal d
Show that if $n = 35$ is used as an RSA modulus then the encryption exponent $e$
always equals the decryption exponent $d$?
What I have so far:
$n = 35$
Therefore $p = 5$ and $q = 7$ or vice versa, ...
4
votes
1answer
440 views
Why is ElGamal considered non-deterministic?
One difference between RSA and ElGamal is that ElGamal isn't necessarily deterministic (while RSA is).
What makes it non-deterministic? Is this advantageous to security? How else does this property ...
2
votes
1answer
366 views
What does SSL use? RSA? El-Gamal? Elliptic curves?
I'm not sure what SSL uses to share the symmetric key to both end users, i.e. at the beginning of the communication. Is it RSA? Or El-Gamal? Or something else?
Thanks!
4
votes
1answer
180 views
How are trapdoor functions developed/found and where can I find existing ones?
Trapdoor functions are a fundamental part of public key cryptography. An example of the most common trapdoor is
Prime Factorization, used in cryptosystems such as RSA
How are these trapdoor ...
2
votes
2answers
415 views
Proof of security for RSA signatures
I am new to here, I was having some problems with a problem I am working on:
"For each of the following variants of the definition of security for signatures, state whether textbook RSA is secure ...
6
votes
2answers
1k views
Definition of Textbook RSA
What is the definition of Textbook RSA?
What are some of the properties of textbook RSA?
How does it differ from other RSAs?
3
votes
1answer
446 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 ...
4
votes
2answers
405 views
How do I solve this RSA instance for m?
How we can solve this equation and get the value of M?
$$8 = M^{13} \mod 33$$
not a computer program, but a mathematical operation.
2
votes
1answer
387 views
Demonstrating the insecurity of an RSA signature encoding scheme
I'm working on problem 12.4 from Katz-Lindell. The problem is as follows:
Given a public encoding function $\newcommand{\enc}{\operatorname{enc}}\enc$ and
a textbook RSA signature scheme where ...
