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
156 views

In RSA, how to make sure that $p-1$ and $q-1$ are still hard to factorize?

See this question. The comment by Brett Hale stated: On the other hand, ensuring $(p - 1)$ has a large prime factor requires very little extra effort. What's actually the 'little extra effort'?
5
votes
1answer
33 views

In PKCS#1 V2.2, should MGF be based on the same hash function that RSA-OAEP-ENCRYPT uses?

In Section 7.1.1 of PKCS#1 v2.2 there are two options for RSAES-OAEP-Encrypt given: Hash MGF Appendix B.2.1 of the same document states that MGF1 is based on a hash function. Is MGF1 based on the ...
5
votes
1answer
163 views

Understanding Genkin-Pipman-Tromer's ground potential, side channel attack on RSA

I'm pretty sure that by now folks might have come across this research from Genkin-Pipman-Tromer (GPT) on extracting the RSA key used by GnuPG (GPG) just by measuring the ground potential. I'm going ...
5
votes
1answer
1k 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
337 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
2answers
953 views

How to verify the integrity of RSA encrypted messages?

I need to encrypt messages using PublicKeyCrypto and send it to the server, where the message should be decrypted. I'm aware of the Padding Oracle Attack and want to apply a server side integrity ...
5
votes
1answer
2k views

Good entropy source for generating openssl keys

I need to generate a CA (4096-bit RSA) and server keys for openvpn and I want them to be "top quality". Here is my plan: gather entropy from multiple sources (saving individual files): FreeBSD ...
5
votes
1answer
342 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
480 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
1answer
445 views

Question about why RSA is hard to attack

I think I understand why RSA is hard to attack but I'd like to get clarification if I actually do. Assume there are two people, Alice and Bob, who are attempting to communicate privately but that we ...
5
votes
1answer
289 views

Safely use CryptSignAndEncryptMessage?

I am developing an application that sends messages which I want to encrypt and sign. The CryptoApi offers a function called CryptSignAndEncryptMessage. The description says, what this function ...
5
votes
1answer
141 views

Encryption scheme like RSA where encryption is the inverse of decryption

In RSA, it is basically equivalent to use the private key $d$ to encrypt as it is to use the public key $e$ to encrypt. They are exactly inverses: $e=d^{-1}$. I need to know, are there other public ...
5
votes
1answer
277 views

How long does it take to decrypt an RSA/ECB encrypted message?

I am working on assignment where I have specific scenarios and I am little bit struggling with this one. Alice sends and email to Bob.For this e-mail, she uses the following method of encryption: ...
5
votes
3answers
934 views

How can I prevent a message replay with RSA?

I am using RSA to encrypt some data but I would like to eliminate the possibility of message replay. By message replay I mean sending a valid message multiple times to the original recipient. It is ...
5
votes
1answer
139 views

How to attack RSA-CRT with large public exponent?

Suppose we have $(n,e)$ and the ciphertext $c$ where the public exponent $e$ is of the same length, 1023-bit, as the modulus $n$. It is also assumed that the factors of $n$ are balanced. The message ...
5
votes
1answer
228 views

Why $e>n^{3/2}$ prevents Wiener's attack

Here's the Wiener's attack as I understand it. Suppose $n=pq$ with $q < p < 2q$, and $d < n^{1/4}/3$ where $ed=k\phi(n)+1$ and $e < \phi(n)$. $$\begin{align*} n-\phi(n) &=n-(p-1)(q-1)...
5
votes
1answer
293 views

Using same modulus for RSA

I know that there exist some attack when using same modulus. Can two different pairs of RSA key have the same modulus? RSA cracking: The same message is sent to two different people problem But ...
5
votes
1answer
1k views

Can you help me understand the Common Modulus Attack in a Lucas Group?

I'm trying to decrypt a message that is encrypted using a LUC encryption scheme and running into roadblocks. I know that with RSA if Alice and Bob use the same public modulus but different encryption ...
4
votes
4answers
451 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
577 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
3answers
661 views

P = NP and current cryptographic systems

I've recently heard some people claiming that if the fact that P = NP is proven, most (all?) the current cryptographic algorithm considered secure like RSA will be unusable in secure systems. My ...
4
votes
3answers
1k 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
2k views

Is RSA in a ECB-like-mode safe for bulk encryption?

Let's say I would like to communicate with my friend using asymmetric/public-key encryption, e.g. RSA. (Note: I do realize that in practice this is done through an intermediate symmetric key, but ...
4
votes
3answers
477 views

Can an ephemeral RSA key give forward secrecy?

Suppose party A generates an ephemeral RSA key and sends the public key to B. Party B then generates a symmetric key, encrypts it with Party A's public key and sends the Ciphertext to Party A. Party ...
4
votes
3answers
789 views

How can mega store my login details and still be secure?

I understand how Mega's encryption works. For a quick summary of all those in the future looking for an answer on this... here is how it works: Upon first signing up for an account you make a ...
4
votes
2answers
217 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
3answers
7k views

RSA Proof of Correctness

Can anyone provide an extended (and well explained) proof of correctness of the RSA Algorithm? And why is it needed? I can't say that this or this helped me much, I'd like a more detailed and newbie ...
4
votes
1answer
268 views

Modular exponentiation on calculator for textbook RSA

How do you encrypt $51$ with public key $(n,e) = (91,23)$ I understand that $c = 51^{23} \bmod 91$. How can I calculate the result on a calculator?
4
votes
1answer
205 views

RSA time function

I am doing a paper on textbook RSA (highschool-level). I am explaining and proving the significance of the public key exponent in time and security. So far, I have encrypted a constant message with a ...
4
votes
2answers
520 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
1answer
2k views

RSA: If n=35, show that e will equal d

Show that if $n = 35$ is used as an RSA modulus then the encryption exponent $e$ always equals the decryption exponent $d$? What I have so far: $n = 35$ Therefore $p = 5$ and $q = 7$ or vice versa, ...
4
votes
1answer
330 views

For RSA keys, is the safety of a given key-length different for signing vs encryption?

I'm wondering if considerations of key-length are different when thinking about signing vs encryption. If for some reason, it was safter to use smaller keys for signing that would be interesting.
4
votes
3answers
227 views

Why are we not using multiple ciphers per message?

I am aware of at least rsa, elgamal-encryption, and variations of elliptic-curves relying on different problems and that those problems are considered hard. However, if someone figures out a way to ...
4
votes
1answer
8k views

HMAC SHA256 vs RSA SHA256 - which one to use

Salesforce recently announced they are moving away from HMAC SHA256 to RSA SHA256. Why did they make that move?. Any technical factors? Is HMAC really easy to break? https://login.salesforce.com/...
4
votes
2answers
288 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
3answers
5k views

Is javascript RSA signing safe?

I'm currently working on a secure open source messaging system (https://github.com/DSMNET/DSMNET). I'm currently using the cryptico.js (https://github.com/wwwtyro/cryptico) library to encrypt all the ...
4
votes
1answer
1k 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
189 views

When is an asymmetric scheme considered broken?

Does the following quote imply that valid encrypted data can be created and decrypted by someone other than the owner of a private key: An asymmetric encryption scheme is considered to be broken ...
4
votes
2answers
126 views

RSA 3072 is 65,536 more difficult to factor than 2048?

If RSA 3072 is equal to 128 bit symmetric and 2048 is equal to 112 bit symmetric then 128-112= 16 and 2^16= 65,536. In that case wouldn't this make 3072 more future proof against quantum computers or ...
4
votes
1answer
104 views

Distribution based integer factorization

The past week I've been looking into - and playing with - algorithms for factoring RSA moduli. From what I understand, it's important that the primes p and q are of the same magnitude as the square ...
4
votes
1answer
407 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
273 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
198 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
3k 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 = 00:c0:fb:55:b3:ed:f5:19:bf:8d:3a:2a:60:e8:bc:...
4
votes
1answer
284 views

Signing a GCM MAC

If I encrypt a message with AES-GCM, is it safe to use the MAC as the hash in a DSA/RSA signature? That is, if someone knows the AES key and nonce, will they be able to generate a different message ...
4
votes
1answer
129 views

Why does choosing the first coprime e greater than half of φ(n) result in the same d (private exponent)

While reading on RSA's algorithm, I attempted a simplified implementation and noticed the following: When choosing the public exponent $e$, if the value chosen is the first coprime after $φ(n)/2$ ...
4
votes
1answer
433 views

How to sign a large file for random-access reading?

I need to write an "Authoring" application which produces large files. These files must be signed so that the "Consuming" application knows that it was authored with a matching key. The consuming ...
4
votes
2answers
72 views

RSA: select $e$ given $n$ and $\varphi(n)$

I have a question for a course I am doing. In an RSA question, it asks "Is it possible to select $e$ in such a way that it coincides with the corresponding private key $d$? If it is possible, provide ...
4
votes
2answers
254 views

Why is 2048-bit RSA always paired with 320-bit ECC?

You may already have noticed that most smart cards ship with 2048-bit RSA support and 320-bit ECC over GF(p) support. You may have already asked yourself "why exactly 320-bit?". Now I remember having ...
4
votes
1answer
229 views

Is the strength of RSA over quadratic or other cyclotomic fields as strong as over the integers?

If we assume the strength of RSA is based on the difficulty of factoring (which I know we can't guarantee) and we compose the modulus of some other quadratic ring that is a unique factorization domain ...