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.
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 ...
1
vote
2answers
100 views
Is semantic security important in a hybrid cryptosystem?
RSA doesn't provide semantic security when used unmodified, and neither does the commonly used PKCS#1 v.1.5 padding scheme for encryption.
Is this a problem for hybrid cryptosystems at all?
My ...
0
votes
2answers
62 views
What is RSA key normalization?
How can I understand the term RSA key normalization? What exactly is done in the process??
Please explain.
1
vote
1answer
389 views
How do I derive the time complexity of encryption and decryption based on modular arithmetic?
I want to calculate the time complexity of two encryption and decryption algorithms.
The first one (RSA-like) has the encryption
$$ C := M^e \bmod N $$
and decryption
$$ M_P := C^d \bmod N. $$
...
0
votes
0answers
81 views
RSA and One Time Password (OTP) service
What is the expert cryptographic opinion on the following?
Assume that there is a web server and a client on web page.
User on the Client calls an OTP web service on the server which
a) creates a ...
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 ...
4
votes
3answers
207 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 as RSA or DSA key from it? If ...
0
votes
0answers
47 views
How compute encrypt and decrypt runtime for agorithm [closed]
I programming RSA algorithm is the following two function in java language in my thesis
...
1
vote
1answer
56 views
What is the most secure way to let Alice “input” her private key, transfer it to the server and decrypt the message?
What is the most secure way to let Alice "input" her private key, transfer it to the server and decrypt the message? (Then destroy the private key on the server)
Every connection is using SSL.
...
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? ...
2
votes
2answers
118 views
Is it safe to use RSA as a proof-of-work system?
Suppose I devised the following challenge-response proof-of-work system:
A server generates a 2048-bit RSA modulus, and uses the "public" exponent (usually 65537) to sign a random nonce a fixed ...
2
votes
1answer
223 views
Attacks on the RSA Cryptosystem
I was reading some articles about attacks on RSA system and I wonder about some generalization of the following theorem.
Theorem (Coppersmith).
Let $N=pq$ be an $n$-bit RSA modulus, where
...
2
votes
1answer
251 views
What happens if an RSA key pair has identical public and private exponents?
Rather, is it possible for big prime numbers?
Classroom examples usually involve smaller primes, so for example if you are given a prime number pair $p = 3$, $q = 13$ you would get $n = 39$ and $e = ...
-1
votes
2answers
468 views
RSA 4096 bit key benchmark
is there any benchmark for RSA 4096bit long keys on general computers ? how many encryption decryption possible per second ? all benchmarks only show 1024 and 2048 benchmarks :(
7
votes
1answer
313 views
Why do all SSH-RSA Keys begin with “AAAAB3NzaC1yc”?
My Friend and I have been generating a few ssh2-rsa keys and noticed that all the public keys began with "AAAAB3NzaC1yc". The similarity extended to "AAAAB3NzaC1yc2EAAAABIwAAAQEA" between two keys I ...
2
votes
1answer
105 views
Why is RSA usually limited to messages up to 1 block
I'm wondering why RSA encryption usually is only used for messages that fit into one block.
For larger messages hybrid encryption in combination with symmetric ciphers like AES seem to be the solution ...
1
vote
3answers
453 views
Is 512-bit RSA still safe for signature generation?
The standard CSP on Windows XP only supports RSA up to 512-bit, which means that it's the maximum key size I can use for authenticity verification of updates. The public key is embedded in the ...
4
votes
1answer
221 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
4answers
412 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?
0
votes
1answer
279 views
Why the following attack in common modulus RSA works?
Suppose that i share a common modulus $N$ with two users $u_1$ and $u_2$ with public, secret keys ($e_a,d_a$), ($e_b,d_b$).
Why then $gcd(V,e_b)=1$ where $V=d_a*e_a-1/$W and $W=gcd(e_b,d_a*e_a-1)$ ...
0
votes
1answer
66 views
Tweaking textbook RSA to make the encryption a Pseudorandom function
Lets say I want to tweak/alter the textbook RSA encryption function to create a pseudorandom function by pre-processing the input.
Suppose I do something simple like add 2 to the input before ...
1
vote
0answers
27 views
Generating Polynomials for the MPQS
I'm going to try and eventually factor RSA-100, but my current QS needs a lot of improvement, so I'm going to try and switch over to the MPQS.
I'm a bit confused as to how the MPQS works, which is ...
2
votes
1answer
75 views
Individual bits of Textbook RSA
This question relates to the underlying RSA assumption. Forgetting about the fact that Textbook RSA is deterministic, I am curious about the assumed strength of the RSA problem.
Does RSA hide all ...
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 = ...
2
votes
1answer
221 views
How much extra information is in an RSA public key?
I'm trying to calculate the size of an RSA public key in Ruby. I've retrieved the key in PEM format, and once I've decoded the base64 part from the PEM format, I get the size in bytes. What I find is ...
1
vote
1answer
125 views
Is this attack for RSA possible?
$N=p·q$ ($p$ and $q$ are prime numbers), $m_1, ..., m_x$ are the messages, $e$ and $d$ are RSA encryption and decryption exponents, respectively.
I am given $e, m_1, m_1^e, m_1^d, ..., m_x, m_x^e, ...
2
votes
2answers
118 views
phi(P*Q) = (P-1) * (Q-1)
I was trying to understand RSA when I encountered the Euler Function. I do understand this: $\phi(P)$, where $P$ is a prime is $P-1$.
However it seems that for a number $N$ such at $N=P\cdot Q$ where ...
1
vote
1answer
61 views
Is there a big RSA Data Set
Is there a big dataset containing RSA public $(n,e)$ and private keys $d$ and primes $p,q$ where $n = p.q$ ?
4
votes
2answers
252 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
2answers
179 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 ...
17
votes
2answers
820 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. ...
1
vote
1answer
130 views
using Post-quantum asymmetric ciphers instead of RSA
We can't trust RSA to encrypt our Emails so what is best post-quantum cryptography system as alternative for RSA which provide good security and don't be breakable? because McEliece cryptosystem looks ...
1
vote
1answer
102 views
RSA Key generation Public exponent too big
I'm currently writing a paper about RSA (a self-chosen subject).
I'm writing about the key-generation in RSA, and I have problem finding the public exponent e.
I have chosen p = 61 and q = 53.
Then ...
0
votes
0answers
76 views
Factorize RSA knowing several N and E
I did a CRT challenge yesterday and there`s one problem I was unable to solve, probably due to my lack of understanding advanced crypto math.
It`s about RSA. There are ten given pairs of N and E ...
2
votes
1answer
97 views
RSA Without Padding?
I've been looking at the weakness with plain/textbook RSA, where the same message is encrypted and sent to multiple destinations. In this case, it is possible to recover the message.
Given that an ...
1
vote
1answer
95 views
Does RSA-OEAP have integrity and authenticity properties?
RSA-OAEP is IND-CCA2 secure (indistinguishable under an adaptive chosen ciphertext attack). Does it also have the INT-CTXT (integrity of ciphertext) and INT-PTXT (integrity of plaintext) properties?
...
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 ...
4
votes
1answer
138 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. ...
5
votes
1answer
355 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 ...
1
vote
1answer
154 views
Weakness in using only one RSA key pair for two-way communication?
In Alice/Bob/Cindy terms (EDIT: and with a little more detail):
Alice and Bob have each securely obtained one key of an RSA keypair from a trusted third party. Alice has one key ($e$ and $n$), Bob ...
1
vote
1answer
188 views
Constructing RSA private key, given public key
As part of a puzzle I was given an RSA 256-bit public key and an encrypted message.
The key itself is very weak, having exponent e = 65537 and modulus N = ...
0
votes
0answers
75 views
Actual weakness RSA [closed]
I need modern trends analysis RSA. Hinek books "Cryptanalys RSA and Yan "Cryptanalytic RSA" have been read. What else?
2
votes
3answers
585 views
Is it safer to encrypt twice with RSA?
I wonder if it's safer to encrypt a plain text with RSA twice than it is to encrypt it just once. It should make a big difference if you assume that the two private keys are different, and that the ...
13
votes
4answers
541 views
Is Wiener's attack on RSA extendable to larger keys with low hamming weight?
Using small private exponents with RSA improves performance.
However, it has been shown (Wiener, 1990) that if $\log d \leq \frac14 \log N$, the private exponent $d$ can be reconstructed from the ...
4
votes
1answer
122 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 ...
2
votes
0answers
99 views
Ring Signature - paper/code difference in trying to solve inverse trap door function?
there is a paper on ring signatures and a python implementation of it here.
The Step 4 in the paper describes $y_s = v =C_k,_v(y_1, y_2, ... y_r)$ for all $1 \leq i \leq r$ where $i \neq s$. The ...
0
votes
2answers
118 views
Breaking RSA, given a special kind of oracle that decrypts related ciphertexts for us
Let $c=E^{RSA}_{e}(w)$ be the ciphertext belonging to the plaintext $w$ if an $RSA$ system is used. Assume that the public exponent $e$ satisfies $e \le 10$. Furthermore, assume there is an oracle ...
0
votes
1answer
137 views
What is a trapdoor permutation?
Can anyone explain to me what a trapdoor one-way permutation is? Is RSA a trapdoor one-way permutation?
Context: I was reading about ring signatures. On page 560, it describes steps to ...
6
votes
4answers
402 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 ...
4
votes
2answers
326 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 ...
