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

1
vote
1answer
87 views

Does it necessary the public key is prime number in RSA algorithm?

I read some books talk about RSA cryptography but I did not understand something when choosing a public key $e$ Sometimes the condition is $1<e<$$\phi(n)$ Where $\phi(n) = p-1 * q-1$ also ...
0
votes
1answer
269 views

Timelock puzzle improvment

I came across this question with this answer about a cryptographic timelock-puzzle that needs approximately 30 years to be solved. There is also an explanation with source code for that puzzle ...
1
vote
0answers
152 views

Existential Forgery on textbook RSA signatures

Can an adversary who haven't seen the message before forge the signature of that message? The adversary has seen $σ_1 = (m_1)^d \bmod N$ and $σ_2 = (m_2)^d \bmod N$ He forges $m' = m_1\cdot m_2$ $σ' ...
0
votes
0answers
24 views

How to compare security parameters of different schemes (Sign-Encrypt, Encrypt-Sign, etc)? [duplicate]

How can one compare the security parameters (confidentiality, integrity, non repudiation, etc.) for different schemes (Sign-Encrypt, Encrypt-Sign, Sign-Encrypt-Sign, Encrypt-Sign-Encrypt)? Are there ...
0
votes
1answer
70 views

RSA Cryptosytsem, choosing $e$ [duplicate]

I am using the RSA crytposytem. I have $p$, $q$ and hence $n$ and $\phi$ however I don't understand how to get $e$ such that $gcd(e,\phi)=1$ Many thanks
0
votes
0answers
116 views

Generation of strong primes

It seems that this is pretty difficult to find large (above 1024 bits) strong primes, or at least such primes p where (p-1) has a very large prime factor. Is there any information regarding the ...
1
vote
3answers
159 views

Maximum length in bits of the product n=pq

If p and q are two 1024-bit prime numbers, would the maximum length in bits of product $n=pq$ be ${1024}^2$ or $2^{1024}$? I think it is ${1048576}={1024}^2$? Also, would the least significant bit ...
0
votes
0answers
87 views

RSA OAEP: prevention of partial decryption of ciphertexts

I'm trying to understand RSA encryption (as a beginner in cryptography). go on this wiki page http://en.wikipedia.org/wiki/Optimal_asymmetric_encryption_padding scroll down to the 2 numbered points: ...
0
votes
0answers
178 views

Cracking RSA with Small exponent 5

I have read following questions - Cracking an RSA with no padding and very small e Small Encryption Exponent where in first it says to run out all the possible m options and second says factor ...
-1
votes
1answer
120 views

Cracking plain RSA by factoring the modulus n

This is the setup: I have both public and private keys of one "instance" of RSA. And I have only the public key of another RSA cryptosystem, but this system has the same modulus as the first one. I ...
0
votes
1answer
243 views

Python. RSA common modulus attack problem

I have: N = /*500 decimal numbers*/ E1 = 3740453 E2 = 4226171 M^E1 = /*500 decimal numbers*/ M^E2 = /*500 decimal numbers*/ I must use RSA common modulus ...
2
votes
2answers
239 views

Is there a way to systematically calculate the public exponent $e$ in RSA?

I'm learning RSA in one of my classes and we were given a problem: $p = 5$, $q = 11$ I have done the following steps: $n = 5 \cdot 11 = 55$ $\phi = (5-1)\cdot(11-1) = 40$ I know that to ...
0
votes
1answer
58 views

special public keys and modulo n

I just picked up cryptography and have some questions on RSA cryptosystem: Say there are two public keys (n, e1), (n, e2), e1 is coprime to e2. They share the same n. Is it possible to find the ...
0
votes
1answer
56 views

what does rsaSha512Sign do?

I have the following function: ...
0
votes
1answer
154 views

OpenSSL RSA same plaintext but different ciphertext

how OpenSSL RSA work ? I generate public (n,e) and private key (n,d) then I encypted a file by : ...
2
votes
2answers
277 views

Can RSA signing be implemented on top of RSA encryption/decryption?

I need to use RSA-SHA256 signing. Unfortunately not all Microsoft CryptoAPI providers support that. It's possible that I might get a handle to a CryptoAPI provider that can just encrypt/decrypt with ...
0
votes
1answer
309 views

Storing AES encrypted RSA private keys on a server

I'm thinking about creating an encrypted messaging web application where users create RSA key pairs, they store the public key on the server for others to see and also store an AES encrypted private ...
0
votes
1answer
120 views

Determining message given cipher-text and public key [duplicate]

Consider the following scenario: Suppose A and B have set up their RSA public keys, namely $(e_a, n)$ and $(e_b, n)$, where the n-value is the same. Also, it happens that the $\gcd (e_a, e_b) ...
0
votes
1answer
103 views

RSA: Fermat-Euler Theorem - coprimality of message and modulus [duplicate]

I understand the implication of the Fermat-Euler theorem and how it applies to RSA and the detailed explanation by user Ninefingers at What is the relation between RSA & Fermat's little ...
3
votes
2answers
914 views

Which attacks are possible against raw/textbook RSA?

The PKCS#1 standard defines multiple padding schemes for signature generation/verification (EMSA-PSS and EMSA-PKCS1-v1_5), and encryption/decryption (EME-OAEP and the less safe EME-PKCS1-v1_5). ...
0
votes
0answers
138 views

Franklin-Reiter related message attack m2 = a(m1)+b

As shown in their paper, https://www.cs.unc.edu/~reiter/papers/1996/Eurocrypt.pdf, if one is given an equation relating the two messages m1 and m2 as well as other information one can crack both the ...
0
votes
1answer
85 views

In RSA, why does Alice's $N$ need to be relatively prime to Bob's $N$?

I was asked this by my professor and I didn't understand the reasoning behind it. If Alice has a the key pair $(p_a, n_a)$ and Bob has the key pair $(p_b, n_b)$, why do $n_a$ and $n_b$ have to be ...
1
vote
1answer
150 views

File format of an $2048$ bits RSA public key

From here, there are $14$ bytes specifying the file format of the key. I am still quite confused about the format bytes. For example, the following public key 30 82 01 0a 02 82 01 01 00 8e a3 d1 c7 ...
0
votes
0answers
83 views

Is a RSA 2048 bits public key secure [duplicate]

I realize servers such as Google, Yahoo, which use RSA has 2048 bits public key. After comparing those keys, I realize that the public keys share a common property, that is first 9 bytes and last 5 ...
1
vote
1answer
223 views

Crypto libary with Commutative Encryption

I want to implement Mental Poker in JavaScript as a toy program and lead in to a larger serious project so I did my research and found Massey-Omura cryptosystem and the Shamir three-pass protocol ...
1
vote
1answer
264 views

Can public key be recovered from ciphertext & encrypted private key?

I'd like to implement something like a write-once public/private encrypted shared secret (no better quick description for the lack of terminology knowledge). I guess, I'm trying to implement HSM. The ...
3
votes
1answer
188 views

Security of RSA with $\gcd(pq, (p-1)(q-1))\ne 1$

The Congress of ThéOùÇa enacted that civilian use of any public-key encryption system is authorized on the territory of ThéOùÇa, subject to meeting certain security requirements published by the ...
0
votes
1answer
51 views

When homomorphic encryption goes wrong?

Consider I have two ciphertext $c_1$ and $c_2$ encrypted using RSA encryption. By definition if I multiply them I'd get $c_1.c_2 \ modN$. My question is what would happen if $c_1.c_2 >N$. Can we ...
1
vote
2answers
250 views

RSA Decryption given n, e, and phi(n)

my cryptography professor gave us this problem for extra credit a while back and I attempted it but I didn't get it correct. I have gone back to it, but I'm even more lost now than I was the first ...
0
votes
1answer
37 views

RSA signature scheme

In RSA signature scheme, it is a common practice to 'sign' the hash value of the message so that the length can be fit. Question: If we have $s=m^d \bmod n$ where $d$ satisfies $ed \equiv 1 ...
0
votes
0answers
59 views

Low exponent attack against RSA

According to this: http://www.cims.nyu.edu/~regev/teaching/lattices_fall_2004/ln/rsa.pdf One can calculate the message m, if there was no padding scheme involved. My question: is it possible to find ...
1
vote
1answer
260 views

rsa public and private keys

I have a question about RSA key generation. This is a simple RSA algorithm: Choose p = 3 and q = 11 Compute n = p * q = 3 * 11 = 33 Compute ?(n) = (p - 1) * (q - 1) = 2 * 10 = 20 Choose e such that ...
1
vote
2answers
105 views

RSA prove $a^{\varphi(n)/g} \equiv 1 \pmod{n}$

I should prove that $a^{\varphi(n)/g} \equiv 1 \pmod{n}$, so I thought I would prove it with primitive roots but I got stuck. Here is the assignment: Let $p, q$ be primes such that $p \ne q$. ...
0
votes
1answer
99 views

RSA CRT modulo reduction

I am working on RSA CRT and there is a point that I don't understand : So we have $n=pq$ and $c = m^e \bmod n$ an encrypted message. To decrypt $c$ with RSA CRT, we have to compute : $d_p = d \bmod ...
2
votes
1answer
264 views

The Boneh-DeMillo-Lipton fault attack (RSA CRT)

I am trying to understand the Boneh-DeMillo-Lipton fault attack on RSA CRT signature. Suppose that we sign a message $m$ with RSA-CRT : $d_p = d \bmod (p-1)$ and $d_q = d \bmod (q-1)$ $s_p = ...
1
vote
2answers
317 views

Use case of RSA CRT

I discovered the CRT version of RSA cryptosystem which is used in many crypto libraries (openSSL, Java...). The use of the Chinese Remainder Theorem improves the speed of decryption so why it's not ...
0
votes
1answer
120 views

Is there any probabilistic version of RSA?

I have now studying the RSA, but I think that is it possible to have some probabilistic version like a random bit string "r" XORed with the key? Is there any probabilistic version of RSA? Thak you ...
2
votes
1answer
97 views

Recover plaintext in passive attack of RSA of coprime public key

I have a situation in RSA like this. Charles sends same message $m$ to Alice and Bob encrypted with $e_A$ and $e_B$ respectively. It happens that he they are under same modulus $n$ and $gcd(e_A, ...
3
votes
2answers
312 views

Small Prime Difference in RSA

In RSA, the $p$ and $q$ should be randomly generated, and they are the same size. The difference between $p$ and $q$ should not be small. Suppose that $u=|p-q|<20$ and $p \times q ...
2
votes
1answer
101 views

Implementation of garbled circuits using RSA

I was just reading these notes on garbled (Yao) circuits and I just stuck trying to figure out how an implementation of Table 1 would work using RSA encryption. In RSA the public key is (n,e). So for ...
1
vote
1answer
207 views

Compare two approaches for cracking RSA key

I came across these questions while studying for a crypto course, does anyone have any ideas on how to answer these? (a) Random prime numbers of size 1536 bits are chosen to generate an RSA modulus ...
7
votes
1answer
600 views

What is the history of recommended RSA key sizes?

One can find up to date recommended key sizes for RSA at http://csrc.nist.gov/publications/nistpubs/800-131A/sp800-131A.pdf for example. In short it suggests a key size of at least 2048 bits. Is it ...
1
vote
2answers
209 views

How do RSA and ElGamal key sizes compare?

I have a rather silly question regarding the comparison of RSA with ElGamal over integers. If you want to compare their performance in the same level of security, does the modulus of both of them need ...
1
vote
1answer
87 views

Breaking RSA moduli

Let suppose that the sizes of factors $p$ and $q$ are $b$ bits. We construct two RSA numbers $n$, $n'$ of same sizes. Can we say that the duration to break these two numbers is two times the duration ...
1
vote
1answer
266 views

How costly is to find millions of large prime numbers for RSA?

Consider I need to assign a large distinct prime number to each element in a large set. This must be deterministic so the function always gives me the same prime to the same value. What is the most ...
1
vote
1answer
93 views

RFC3447 OBJECT IDENTIFIER semantic

http://tools.ietf.org/html/rfc3447#appendix-B.1 ...
0
votes
1answer
144 views

Is this chat protocol safe?

I am in the design phase of a secure chat application at the moment. I am trying to make this as secure as possible. The Serverprovider should not have access to the messagedata. So my idea was the ...
-1
votes
1answer
275 views

RSA given q, p and e?

I am given the q, p, and e values for an RSA key, along with an encrypted message. Here are ...
2
votes
1answer
231 views

what are DP and DQ in Encryption by RSA in c#

I want to know about these tags in RSA Encryption by private Key. when I use this code: ...
2
votes
1answer
301 views

Calculate the RSA private exponent from the CRT parameters

I am trying to make the RSA structure of Openssl manually, knowing the public key ($n$, $e$) and the CRT parameters $p$, $q$, $d_P$, $d_Q$, and $u = q^{-1} \mod p$. That is, I want to get the $d$ ...