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

5
votes
1answer
2k views

RSA-PSS salt size

One of the inputs of RSA-PSS signing and verification is the salt size. According to PKCS#1, you must know the salt size before the verfication is carried out. However, this makes interoperability ...
5
votes
1answer
793 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 ...
5
votes
1answer
411 views

What is the harm if I publish an encrypted RSA private key publicly?

What is the harm if I publish an encrypted RSA private key publicly? Or in this case, what is the harm if I publish many thousands or millions of them? Assuming that the private key is encrypted ...
5
votes
1answer
609 views

Are there any MGF1 and OS2IP functions available in C?

I need MGF1 and OS2IP functions, as defined in the PKCS #1 v2.1: RSA Cryptography Standard. Is there anything available in OpenSSL, or any other open C library?
5
votes
1answer
760 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 ...
5
votes
1answer
287 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 ...
5
votes
1answer
208 views

How can I take advantage of repeated patterns in non random RSA prime factors?

I am researching vulnerable RSA moduli which are composed of primes generated with poor entropy. Having a list of these primes I searched for variable sized repeated patterns among them and I noticed ...
5
votes
1answer
267 views

Proof that padded RSA is CPA-secure

I'm referring to page 383 of J. Katz and Y. Lindell's Introduction to Modern Cryptography. The book presents a padded RSA: ${\bf Key Generation:}$ same as Textbook RSA (given security parameter ...
5
votes
1answer
248 views

In textbook RSA with low public exponent, how big does a random message needs to be?

Assume RSA with a public modulus $N$ of $n$ bits, a small odd public exponent $e$, plaintext $M$ a random non-negative integer less than $2^m$ for some integer parameter $m$, with $M\mapsto C=M^e\bmod ...
5
votes
0answers
203 views

Security of RSA for paranoids with padding?

RSA for Paranoids (RSAP) (in cryptobytes v3n1), also known as Unbalanced RSA, is a variant of RSA proposed in 1995 by Adi Shamir, as a mean to increase the RSA public modulus size while keeping ...
5
votes
0answers
485 views

Bleichenbacher 1998 “Million message attack” on RSA

I have been reading Bleichenbacher's 1998 paper on a forged message attack on RSA. The paper assumes access to an Oracle that takes a ciphertext $c$ and will check the decrypted text for valid PKCS #1 ...
4
votes
4answers
405 views

Where does the $\varphi(n)$ part of RSA come from?

$e d \equiv 1 \pmod{\varphi(n)}$ Where does the $\varphi(n)$ part come from? How did the inventors of RSA arrive at $\varphi(n)$?
4
votes
4answers
411 views

Why $n=pq$ with $p=2p'+1$ and $q=2q'+1$ instead of just $n=p'q'$ for RSA crypto?

For RSA cryptography, we know that the modulo $n$ is a product of two big prime numbers(say $p$ and $q$). However, in some documents I see an extension of $p=2p'+1$ and $q=2q'+1$ with $q'$ and $p'$ ...
4
votes
2answers
504 views

uniqueness of the RSA public modulus

What is the probability that two separate RSA public moduli are the same? For example, consider a 2048-bit modulus. The number seems to be huge, but the choice for prime factors p and q is much more ...
4
votes
2answers
557 views

Why are RSA key sizes almost always a power of two?

I know that other bit sizes are possible, e.g. this HTTPS server seems to have a 9000 bit key https://www.ssllabs.com/ssltest/analyze.html?d=qqq.gg, but it's very rare that one sees a key not of size ...
4
votes
1answer
916 views

How many RSA keys before a collision?

I was wondering how many possibilities of private/public keys there are? If a million people for whatever reason tried to generate 5keys each in the same minute (on the same date and time) is there a ...
4
votes
4answers
5k views

Why is padding used for RSA encryption given that it is not a block cipher?

In AES we use some padded bytes at end of message to fit 128/256 byte blocks. But as RSA is not a block cipher why is padding used? Can the message size be any byte length (is the encrypting agent ...
4
votes
3answers
348 views

How to perform authentication without central server in P2P?

How you be sure that the man who you're talking with is the one who you think he is? I.e. how to perform authentication in P2P network without central trust server or Certificate Authority? I'm just ...
4
votes
3answers
660 views

What is the likely cause the RSA algorithm gives back plain text in this case?

Text book question of Chapter 9 of "Crypto and Network Security" by William Stallings: When using the RSA Algorithm — if a small number of repeated encodings give back the plain text, what is the ...
4
votes
2answers
1k views

Why should the RSA private exponent have the same size as the modulus?

Consider the generation of an RSA key pair with a given modulus size $n$ and a known, small public exponent $e$ (typically $e = 3$ or $e = 65537$). A common method is to generate two random primes ...
4
votes
2answers
153 views

Does a high exponent compensate for a low degree of certainty?

If a RSA certificate is created with a low degree of certainty, does the value of the exponent compensate for this? I'm asking because certain implementations of key generation software hide the ...
4
votes
2answers
4k views

Cracking plain RSA without private key

I was wondering whether plain RSA encryption can be cracked given: The public key A plaintext of a known cipher text(s). In other words the decrypted message from an encrypted one (but without ...
4
votes
2answers
350 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
2answers
486 views

Does RSA padding have to be unpredictable if the payload is?

I'm trying to understand the precise requirements on padding when using RSA for encryption. Suppose Alice uses RSA to encrypt a payload $M$ that cannot be guessed (say, a random nonce): Alice send ...
4
votes
1answer
288 views

Can you explain Bleichenbacher's CCA attack on PKCS#1 v1.5?

I've studied that the Bleichenbacher's CCA attack on PKCS#1 v1.5. is a base to many versions of attacks in the area. I'm trying to understand that attack, but every explanation I saw starts with the ...
4
votes
2answers
166 views

how to iteratively calculate a^emod n with modulus n sized 4096 bits

In most sites the exponent of the RSA public key is 24 bits. But the modulus can get to 4096 bits size. I have an accelerator that can get max. 2112 bit size modulus. It calculates ...
4
votes
1answer
647 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
476 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
2k 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
2k views

Why DSA cannot be used for encryption?

Here it is mentioned that DSA cannot be used for encrypt. But Both RSA and DSA can be used to generate public and private keys, right? (Or am I wrong?). Then why can't I use the DSA public key to ...
4
votes
1answer
810 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
1answer
155 views

Solve a Modular Exponentiation

It might be common, but if we had to solve an equation like this $m=s^{e}$ mod $n$ where $m,e,n$ are known. How can we find $s$. What optimisations could be applied? And what would the complexity of ...
4
votes
3answers
179 views

Why can an RSA signature be authenticated ONLY with the signer's public key?

I'm an undergraduate Math student currently taking a cryptology course. I have a question about the RSA signature authentication mechanism. An RSA signature can be authenticated with the public key ...
4
votes
1answer
193 views

how to use common modulus attack?

I am struck with the following problem: Let Alice, Bob, Chris and Eve communicate over a public network. They encrypt all messages they send using RSA system. Bob and Chris have the RSA modulus ...
4
votes
1answer
142 views

Is knowing the private key of RSA equivalent to the factorization of $N$?

Given the RSA modulus $N$ the fastest method to factor it is of sub-exponent order. But, now if I know the private key $d$ of RSA, does that mean I can factor $N$ efficiently?. It intuitively seems ...
4
votes
1answer
118 views

Difference RSA keypair creation openSSL and openPGP?

Creating a 2048bits RSA keypair I figured that doing this using openssl takes as an input 32bytes of "randomness" from /dev/urandom gpg (openGPG) takes as input ...
4
votes
1answer
195 views

Timing Attack on RSA

So far I have researched on timing attack on RSA, We all know the ransomware named Cryptolocker it uses RSA 2048 bit encryption. Now is it possible to break the encryption using timing attack. I have ...
4
votes
1answer
646 views

Recent attacks on RSA

At Blackhat 2013 this week, there was a talk saying RSA is (essentially) doomed in the near future. networkworld.com ~ “Black Hat: Elliptic curve cryptography coming as smarter algorithms threaten ...
4
votes
1answer
171 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? ...
4
votes
2answers
784 views

Homomorphic cryptosystems in RSA

Hopefully Crypto can help me understand homomorphic cryptosystems. I'm designing a high score server for a game I made, and because of facets in the language i'm using, the player would be able to ...
4
votes
1answer
243 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
2answers
465 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 ...
4
votes
1answer
237 views

Adi Shamir's secret database of all primes

I was going through these presentation slides (PDF) on Crypto 2013. It summarizes the paper, Factoring RSA keys from certified smart cards: Coppersmith in the wild. In the last slide, it was ...
4
votes
2answers
140 views

How can one encrypt with RSA (or ElGamal) without revealing whom the ciphertext is intended for?

Imagine Alice wants to encrypt for Bob and post this encryption publicly, so that only Bob can decrypt but no one can other than Alice or Bob tell that the message was encrypted for Bob. The naive ...
4
votes
1answer
320 views

RSA Encryption and Signature - Weak Padding

Assume that I have an plaintext $m$ and it is padded with $randompad||00||m$ and then it is encrypted with RSA and a public encryption key so we get the encrypted $Sm$. Then to assure its integrity ...
4
votes
1answer
263 views

What signature schemes allow recovering the public key from a signature?

It seems to be possible to retrieve the (public) key used for creating an ECDSA signature just from the signature alone. This seems like an interesting property; as far as I know, RSA doesn't share ...
4
votes
2answers
947 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 ...
4
votes
1answer
440 views

is this RSA private key valid?

is this RSA private key valid? First, here's the RSA private key in question: ...
4
votes
2answers
188 views

State of the art RSA key generation

I would like to know if there is an algorithm to generate a RSA key at the state of the art of the present cryptanalysis. Beside the key lenght I know there are some weakness in the choice of prime ...
4
votes
2answers
390 views

RSA least significant bit oracle attack

I have been reading up on RSA attacks and came across one that could be called a least-significant-bit (LSB) oracle attack. For the sake of clarity lets define RSA primes $(p, q)$, private key $d$ ...