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.
4
votes
1answer
141 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. ...
4
votes
1answer
942 views
Common modulus attack on RSA when the 2 public exponents differ by a single bit
This is an exam question an i have no idea how to recover the message m.
John wants to send an encrypted message to mary who has a pair of RSA keys, However, John does not know Mary's public key and ...
4
votes
2answers
200 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
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 ...
4
votes
2answers
411 views
Is a RSA-signature of some identifying data a safe way to implement a license key?
I have this idea of implementing a license key:
After the user downloads the program, he connects to a website and sends his Windows product ID.
The website, then, sends this back to him with a ...
4
votes
2answers
2k 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 ...
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
2answers
404 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.
4
votes
2answers
762 views
How to calculate the time it'll take to crack RSA or DH?
Sometimes the easiest way to describe security of a type of cryptography is to say that "the time it takes to solve for an x-bit key would be y years". How would one go about doing such a calculation ...
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 ...
4
votes
1answer
85 views
In RSA, how to make sure that $p-1$ and $q-1$ are still hard to factorize?
See this question. The comment by Brett Hale stated:
On the other hand, ensuring $(p - 1)$ has a large prime factor requires very little extra effort.
What's actually the 'little extra effort'?
4
votes
2answers
331 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 ...
4
votes
1answer
113 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 ...
4
votes
1answer
224 views
Calculating RSA private exponent when given public exponent and the modulus factors using extended euclid
When given p = 5, q = 11, N = 55 and e = 17, I'm trying to compute the private key d.
I can calculate phi(N) = 40, but my lecturer then says to use the extended Euclidean algorithm to compute d. ...
4
votes
1answer
123 views
Why does OAEP have 2 rounds with 2 random oracles?
I strive into understanding why OAEP has two rounds of computations and not just one. I.e: Wouldn't it be safe to hash the random number r and XOR it with the original message?What security risks if ...
4
votes
2answers
542 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 ...
4
votes
1answer
135 views
Question about why RSA is hard to attack
I think I understand why RSA is hard to attack but I'd like to get clarification if I actually do.
Assume there are two people, Alice and Bob, who are attempting to communicate privately but that we ...
4
votes
1answer
453 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 ...
4
votes
1answer
179 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 ...
4
votes
1answer
198 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
3answers
244 views
Preventing message replay with RSA
I am using RSA to encrypt some data but I would like to eliminate the possibility of message replay. By message replay I mean sending a valid message multiple times to the original recipient. It is ...
4
votes
0answers
139 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 ...
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, ...
4
votes
2answers
253 views
Are there any standards of multi-prime RSA key generation?
FIPS 186-3 specifies a method to generate DSA parameters.
Is there anything similar (official standard or widely-accepted recommendation) that shows how to generate the primes for multi-prime RSA?
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.
3
votes
2answers
285 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 ...
3
votes
3answers
299 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?
...
3
votes
2answers
134 views
Textbook RSA to Realworld RSA
Is there a paper or link where it explains , how the plain vanilla Textbook RSA is actually implemented in practice with all the padding and stuff ?
basically i want to know the intricacies of ...
3
votes
3answers
91 views
Can the encryption exponent e be greater than Ï•(N)?
So I was just wondering in RSA, can the encryption exponent e be greater than Ï•(N)??
For an examples sake, lets just say N = 707, so p = 101 & q = 7. So, we have Ï•(707) = 600.
Can I have e = ...
3
votes
1answer
166 views
What's the main difference between Pohlig-Hellman and RSA?
Both Pohlig-Hellman and RSA perform encryption and decryption by exponentiation modulo some integer ($p$ prime for PH, $n$ composite for RSA). They both use a key $e$ as the exponent to encrypt a ...
3
votes
3answers
427 views
What is the likely cause when this happens in RSA Algorithm
In using the RSA Algo , if a small number of repeated encodings give back the plain text , what is the likely cause ( Text book question of Chapter 9 ,Crypto and Network Security , William Stallings ...
3
votes
2answers
231 views
How does the cyclic attack on RSA work?
I am trying to get the idea of cyclic attacks againts assymetric RSA encryption.
Taken from Handbook of applied cryptography .
Let $k$ be a positive integer such that $$c^{(e^{k})} = c\mod n ...
3
votes
2answers
456 views
Difficulty of breaking RSA for a given key size
Is it true that breaking a 1024-bit RSA key is as difficult as breaking a 128 bit symmetric key (e.g. AES)? I know that breaking a RSA key is equivalent to factoring the modulus $N$. To factor it, you ...
3
votes
1answer
561 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, ...
3
votes
1answer
133 views
When is an asymmetric scheme considered broken?
Does the following quote imply that valid encrypted data can be created and decrypted by someone other than the owner of a private key:
An asymmetric encryption scheme is considered to be broken ...
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 ...
3
votes
3answers
460 views
Why hash or salt when signing?
I've seen an example of how to sign using RSA. Besides the signing itself (s = m^d mod n) it also hashes and adds an IV.
Why is that needed?
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 ...
3
votes
1answer
158 views
What is the property of RSA where N=e?
In RSA, suppose we know that $e=N$ and we are given the value of $e$.
($N = p\cdot q$ for some large primes $p$ and $q$; $\gcd(e, \varphi(N) = 1)$
Can we calculate $d$ ($d = e^{-1} \mod ...
3
votes
1answer
119 views
How to find an element of high-order in an RSA group?
Is this even possible? The RSA group is not cyclic, so usually you wouldn't find a generator for accessing all group elements.
What happens if you use the RSA group in a scenario where you want that ...
3
votes
1answer
71 views
Why work in a subgroup QR(n) of an RSA group $Z^*_n$?
I sometimes read in papers that a (sub-)group generator $g$ is taken from $\mathrm{QR}(n)$ instead of $\mathbb{Z}^*_n$, where $n = p \cdot q$ and $p$ and $q$ are prime. Is there a reason for this? ...
3
votes
1answer
154 views
RSA algorithm's license free or paid?
I checked RSA's patent application, which was registered in 1983. As patents don't last more than 20 years, it seems to me it should be free. But my friend said to use RSA I have to buy a license from ...
3
votes
1answer
109 views
Combining AEAD with RSA
'Hybrid' encryption, where we combine symmetric encryption with public-key cryptography, is pretty 'tried and tested'.
To summarise, we generate a symmetric key and encrypt it using RSA. We would ...
3
votes
2answers
181 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 ...
3
votes
1answer
244 views
Get RSA PlainText without Knowing Private Key
If I have an algorithm,RSA-Crack(), that, for a given RSA public key (n,e), is able to decrypt 1% of the messages encrypted with that key (without knowledge of the corresponding private key).Can there ...
3
votes
1answer
213 views
is this RSA private key valid?
is this RSA private key valid?
First, here's the RSA private key in question:
...
3
votes
1answer
81 views
implementing long term archive encryption
Let's say I want to create private archives for the long term (e.g. more than 30 ). The archives' sizes could be anywhere from 1 GB to 30 GB. As far as I understand I could go down two ways:
The ...
3
votes
3answers
315 views
How do ciphers change plaintext into numeric digits for computing?
For example, in RSA, we use this for encryption: $ciphertext = (m^e \mod n)$ and for decryption.
If our message is "hello world", then what number do we have to ...
3
votes
2answers
706 views
How do digital certificates work, and why is it not possible to reverse engineer one from a signed file?
Digital certificates are used quite commonly these days, for signing files. They are used by various operating systems to ensure reliability and security. For example, Android requires that each of ...
3
votes
1answer
438 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 ...
