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
1answer
122 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 ...
1
vote
1answer
57 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.
...
4
votes
3answers
209 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 ...
2
votes
2answers
210 views
RSA private key format for Mega
I've been trying to reverse engineer Mega's (mega.co.nz) API calls. And stopped on the step where client needs to decrypt session id with provided RSA key. I can get key data, but I have no idea how ...
3
votes
1answer
72 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
109 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 ...
7
votes
1answer
318 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
257 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 = ...
4
votes
1answer
250 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. ...
0
votes
1answer
288 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)$ ...
4
votes
4answers
415 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?
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 ...
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 ...
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
2answers
122 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$ ?
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
1answer
228 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 ...
2
votes
1answer
227 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
106 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 ...
3
votes
2answers
189 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 ...
-1
votes
2answers
497 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 :(
0
votes
0answers
77 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 ...
1
vote
1answer
133 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 ...
2
votes
1answer
101 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 ...
3
votes
1answer
249 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 ...
1
vote
1answer
96 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?
...
4
votes
1answer
144 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. ...
1
vote
1answer
165 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
193 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
77 views
Actual weakness RSA [closed]
I need modern trends analysis RSA. Hinek books "Cryptanalys RSA and Yan "Cryptanalytic RSA" have been read. What else?
4
votes
2answers
261 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?
1
vote
2answers
390 views
Decrypt digital signature using RSA public key with openssl
I have a digital signature that was created using the following algorithm: a SHA-256 hash of the body of the message is calculated. It is then signed using an RSA private key and the result is ...
2
votes
0answers
101 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 ...
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 ...
2
votes
3answers
596 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 ...
0
votes
1answer
141 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 ...
0
votes
2answers
119 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 ...
4
votes
2answers
339 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 ...
6
votes
4answers
405 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 ...
2
votes
1answer
137 views
Why do we need in RSA the modulus to be product of 2 primes?
I think I roughly understand how the RSA alorithm is working.
However, I don't understand why we need the $N$, which we use as a modulus, to be $pq$ for some large primes $p, q$.
I vaguely know it ...
1
vote
2answers
118 views
RSA keys finding when messages are known
I have this situation, where, in a game, people send messages to each other (game moves etc...) These messages need to be encrypted, and should only be readable by the destination person. I am using ...
3
votes
1answer
168 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 ...
1
vote
1answer
108 views
RSA encryption input range - plaintexts that map to ciphertexts?
According to the wiki article on the RSA encryption function, the valid range of input $m$ is $0 \leq m \lt n$. However I have found that the following values of $m$ always return themselves when ...
1
vote
3answers
461 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 ...
2
votes
1answer
155 views
What is the strength of unpadded RSA?
I would like to use unpadded RSA for homomorphic encryption in a toy P2P game, for things like fair coin flips and shuffling.
How many bits of security does unpadded RSA have, in relation to its key ...
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:
...
2
votes
2answers
423 views
Is RSASSA-PKCS1-v1_5 a good signature scheme for new systems?
Is RSASSA-PKCS1-v1_5 a good signature scheme to recommend that people use in new systems? Is it believed to be secure and represent the state-of-the-art in RSA-based signatures?
I understand that ...
