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

2
votes
3answers
789 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, $\phi(N)...
2
votes
1answer
94 views

Is there an asymmetric algorithm that can perform double encryption?

I'm looking for any asymmetric algorithm can perform the serial encryption, by serial I mean double or more encryption with different key(same key size). RSA can not do it since the cipher of the ...
2
votes
2answers
108 views

Implementing RSA with small integers in CUDA

I have found some researches dedicated for speeding-up RSA calculations using CUDA. But I am wondering how they do that, given that the biggest unsigned int that could be declared in CUDA is 64 bit. ...
2
votes
2answers
96 views

How can a message encrypted with the public key be decrypted with the private key? [duplicate]

I've been reading about encryption and have a basic understanding of the concept. What I don't understand, however, is how a calculation with one key can result in a number that, through calculation ...
2
votes
1answer
97 views

Plaintext and ciphertext block sizes

How can you determine the largest plaintext block size and smallest ciphertext size if you used RSA with $n=59768553302699443$ using an alphabet with $27$ characters?
2
votes
1answer
215 views

Lattice based attack on RSA

Let $n=pq$ be the RSA module and at least one of $p,q$ is a weak prime.It is proved that the number of such $1024$bit $n$ is at least $2^{759}$. With lattices we can factor these $n$ in a second (I ...
2
votes
2answers
100 views

RSA and difference between factors

As I understand, for RSA $n = p \cdot q$. For the key to be safe enough from getting factored, $p$ and $q$ have to be far from each other. How far do they have to be? For example, if I have two $1024$-...
2
votes
2answers
127 views

Why does the time complexity of RSA encryption and decryption depend on the size of the modulus?

I would think that the time complexity would depend on the exponent, not the number of bits in the modulus. For example, if the exponent were 5, using the "naive" method, we would perform 5 ...
2
votes
1answer
153 views

Help understanding basic Franklin-Reiter related message attack

I am trying to understand this attack at the most basic level. I set up the following basic scenario: Let the public encryption exponent, e = 3. Let p, be some arbitrary but known (to the ...
2
votes
1answer
78 views

Diffie-Hellman using a different modulus on both sides

For Diffie-Hellman Key Exchange, the used modulus is the same throughout the process. Is it possible to use 2 different for both sides? For example, $A \gets M^{d_1} \pmod{n_1} $ $B\gets M^{d_2} \...
2
votes
1answer
88 views

Is there really any way to nullify or avoid MITM attacks?

The question pretty much sums it up. Is there any way to make an attacker who is successfully performing an MITM attack to actually not be able to read or change the messages? Assuming there is no ...
2
votes
1answer
133 views

Security impact of signing small data using RSA

I have an application which consists of a client and a server. Both have a pair of public and private key (RSA). For communication, both sign their messages and send them to the other part. So a ...
2
votes
1answer
291 views

Why isn't Rabin-Williams cryptosystem widely used?

I think we all know RSA. And of course we also know DJB (a.k.a. Daniel J. Bernstein). Now some already have noticed that he has an opinion towards cryptographic questions. In his 2008 paper ("RSA ...
2
votes
1answer
92 views

Retrieve value of private key after encryption with the public key

Is there a way to find an RSA private key after it is encrypted with the corresponding public key? Does there exist an algorithm to recover the private key in this special case?
2
votes
1answer
520 views

How multiplicative property of RSA can be exploited

It is known that RSA has the multiplicative property $E(m_1) \cdot E(m_2) = E(m_1 \cdot m_2)$ because $m_1^e \cdot m_2^e = (m_1 \cdot m_2)^e \pmod n$ But how can this property be used to break ...
2
votes
1answer
178 views

What use is the signature without the message under RSA?

Using RSA for signing & verification, is there a way to take a valid signature for an unknown message, and for someone else to generate a valid signature using a different key against the valid ...
2
votes
1answer
668 views

Deterministically generate a RSA public/private key pair from a passphrase (with sufficient entropy)?

Is it possible to deterministically generate public/private RSA key pairs from passphrases? Would giving the (key generating) algorithm data made from key-stretching the passphrase (instead of a ...
2
votes
1answer
490 views

Precomputation attacks on RSA

Are precomputation attacks - such as outlined in RFC 3610 chapter 5 - possible on RSA PKCS#1 v1.5 signature generation? If yes, are such attacks taken into account when calculating the cryptographic ...
2
votes
2answers
1k views

RSA Key Generation Parameters - public exponent, certainty, string-to-key count

I want to know what values are appropriate for the public exponent and certainty when generating an RSA Key (for example using Bouncy Castle RSAKeyGenerationParameters function). What is the ...
2
votes
1answer
956 views

Why should a signature use PSS padding in RSA?

Suppose I send a message using AES (private keys already negotiated securely) and I send a hash of this message using RSA (encrypted with private key) with OAEP to verify the authenticity and ...
2
votes
1answer
262 views

RSA key length choice for TLS when confidentiality not important?

I've a couple of questions about this, the scenario is embedding a key pair in a hardware device which will speak with other hardware devices over tls. computing resources are an issue so i want to ...
2
votes
1answer
747 views

Generate key pair deterministically from a particular seed [duplicate]

I've been reading "SQRL Secure QR Login" at Gibson's website, and I'm wondering if there is a way to generate an RSA private/public key-pair based on some cryptographically secure input, so that if ...
2
votes
2answers
176 views

Does it necessarily mean that an RSA moduli generated with poor randomness is not random?

In 2012 a group of researchers collected a large amount of RSA moduli and calculated their greatest common divisor in order to find common factors between them. By finding a common factor they could ...
2
votes
1answer
1k views

How is text converted to a number for RSA? [duplicate]

According to http://en.wikipedia.org/wiki/RSA_%28algorithm%29#Key_generation the key length is the number of bits in n. So how can a message of many megabytes (millions of bits) be modded by a 1024 ...
2
votes
1answer
69 views

Comprehension question on a signature protocol based on the RSA assumption

We have the following two-party protocol between Alice and Bob. Alice sends messages $m_1, m_2, \ldots \in_R \mathbb{Z}_n^*$ to Bob and Bob signs these values by calculating $v_1, v_2, \ldots \in_R \...
2
votes
1answer
97 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. ...
2
votes
1answer
591 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
2answers
240 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 ...
2
votes
1answer
58 views

How can I show RSA OAEP IND-CPA secure

How can I show, that RSA with OAEP is IND-CPA secure by using G,H one way function?
2
votes
1answer
78 views

Preserving Confidentiality and Integrity in a Public channel

Let's say I've got two people that are trying to talk in a public channel $A$ and $B$ and they want to preserve their confidentiality and integrity. Which cryptographic algorithm would they want to ...
2
votes
1answer
86 views

Attack on textbook RSA with small messages

We learned in class that if Alice wants to send a small message $m$, such that $m < N^{\frac{1}{e}}$, so we can break the system using $e$-th square of $m^e$. But what if Alice knows this flaw and ...
2
votes
1answer
164 views

Modular Arithmetic in RSA

Consider the following the following RSA public key $pk = (N, e) = (1457, 1307)$. (a) Knowing that $187^2 \equiv 1 \pmod {1457}$ find the factorization of $N$. (b) Given the factorization of $N$ ...
2
votes
2answers
117 views

How do you communicate the hash function used with RSA signing?

When it comes to RSA signing, I understand why you need to hash the data before signing it, but don't you need to communicate what hash algorithm you use to whoever will need to verify the signature? ...
2
votes
1answer
59 views

Why can we ignore $y$ when using the extended Euclidean algorithm to calculate an RSA decryption exponent?

I have a follow-up question about the extended Euclidean algorithm, as applied to RSA key generation, described in this answer. Let us say we have $p=5$, $q=11$ and $e=17$, so that $N=55$ and $φ(N)=...
2
votes
1answer
272 views

RSA signatures without padding

Suppose I have a message $M$ for which I generate an RSA-2048 digital signature as follows: $H = H(M)$, $H(M)$ being the SHA-256 of the message $M$ $S = H^d \bmod N$ Assume $N = pq$ is properly ...
2
votes
1answer
206 views

Given only RSA public key parameters, what security issues might I be able to detect?

I'm attempting to automate some checks against a large list of .NET assemblies, and want to include a test to see if the RSA parameters used to sign the assemblies are sensible. However, since I don't ...
2
votes
1answer
205 views

RSA public key exponent generation confusion

Quote from Wiki: $e$ having a short bit-length and small Hamming weight results in more efficient encryption — most commonly $2^{16} + 1 = 65537$. However, much smaller values of $e$ (such as $3$) ...
2
votes
1answer
276 views

2048-bit RSA Decryption

If a message is encoded with 2048 bit RSA. The ciphertext is $M^e mod N$. In some cases, the message is short, $ M \approx 10^{20} $. With a high probability, $M$ can be written as $M = ab$ with $a, b ...
2
votes
1answer
437 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 ...
2
votes
1answer
179 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, e_B)=...
2
votes
1answer
282 views

Small Encryption Exponent

I am trying to crack an unpadded RSA set up for a homework. I have public key (R,e) and encrypted message E. ...
2
votes
1answer
148 views

public key delivery without third party

I am currently working on an anonymous P2P file sharing application and I am elaborating some already existing solutions. Some of them allegedly provide point-to-point encryption using RSA public/...
2
votes
2answers
175 views

Understanding math behind RSA key derivation [duplicate]

I was reading through the key derivation for RSA. Here are the steps per wiki - Select strong primes $p$ and $q$ such that $pq = n$ $\phi(n)$ = $(p-1)(q-1)$ select $e$ such that $e$ and $\phi(n)$ ...
2
votes
1answer
4k views

What is the difference between SHA256WITHRSA and SHA256WITHRSAENCRYPTION digest algorithms?

I installed djigzo on my android phone and I want to use it for smime mail. I don't know the difference between choosing SHA256WITHRSA and ...
2
votes
1answer
275 views

Short length asymmetric encryption?

I want to send out short messages to the world which listeners could verify to be send from me. The way this is usually done is to encrypt the message with a private key where the readers decrypt it ...
2
votes
1answer
129 views

Usability of padding scheme in blinded RSA signature?

In Wikipedia's article on Blind signature, in the section Dangers of blind signing which describes RSA blinding attack one reads the following This attack works because in this blind signature ...
2
votes
1answer
387 views

What exactly is inside a private key?

May sound stupid to many, but I would like to have some pointers on what exactly is contained inside a private key. I have decent understanding of public/private keys/certificates (have created them ...
2
votes
2answers
3k views

How do I calculate the private key in RSA?

Given $n=pq$ for $p,q$ known, I can calculate $\phi(n)$. $e$ is selected such that $\gcd (e,\phi(n)) = 1$. Using this, how do I calculate the RSA private key? Example: I have $n = 35$, with $(...
2
votes
1answer
223 views

Good Encryption Exponent

I have placed a bet that I can create a public key such that my adversary will not be able to crack (decrypt) it for at least one week. For my primes $p$ and $q$, I chose very large numbers that are $...
2
votes
1answer
111 views

Verifying a Signature

Alice publishes $(n,e)$ where $n$ is exponential modulus and $e$ is the public key. We have $n=80$ digit number and $e=3$. Bob, in correspondence with Alice, asked Alice to prove she is really Alice, ...