Tag Info

Hot answers tagged

11

The security of every single cryptographic algorithm(*) of any kind is ultimately based on: "many people looked at it for a long time and did not find a way to break it". Security proofs boasted by some algorithms are quite useful but they don't actually prove security, they move it (a security proof is a reduction to another problem which has to be assumed ...


10

If we consider an RSA modulus $N$ of $n$ bits ($n=2048$ in the question) product of $k$ primes of about $n/k$ bits, how high can be $k$ without loosing security? That's a problem studied even before Multiprime-RSA was named, with no definitive answer other than: we can't err on the unsafe side with $k=2$. Why would we want $k>2$? For classical ...


10

Ricky's link answers your main question in the comments (that knowing the private key is equivalent to knowing the factorization of $N$). But your "attack" is unfortunately part of a class of properties which might appear insightful at first, but which eventually boil down to something like this: "find integers $(m,k)$ such that $m+kn$ is a perfect square" ...


9

Actually, that was proposed here back in 1998 (sorry, an electronic version of the paper does not appear to be on the web) -- the author claimed a modest speedup in the private operations. However, that speed up would appear to be about the same if you just did "multiprime RSA", that is, selected an RSA modulus of the form $pqr$ for three distinct primes ...


9

The question asks how to systematically pick the public exponent $e$ in RSA. I'll stick to public modulus $N$ that is the product of exactly two distinct odd primes $p$ and $q$, but the choice of $e$ is not fundamentally different in multiprime RSA. What's an acceptable public exponent $e$? The public exponent in RSA should be an integer $e>1$ with ...


8

I don't think idea 1 can be made to work at all. The main point is that in order to generate a correct secret decryption key, the key generator must know the order of $\mathbb Z^*_n$, i.e., the totient of the modulus $n$. The generator knows that $n=p \cdot q$, where it believes that $p$ and $q$ are primes, and so it believes that the totient is ...


8

Rather than making an overly long question even longer, I post this as an answer. As part of the update process of the French security recommendations linked in the question, I suggested (June 2013) a waiver for the requirement/recommendation that $e>2^{16}$ when using a padding scheme with a security proof. It was kindly refused (within 6 weeks), with ...


8

We want a non-trivial factorization of a moderate odd integer $n$ into positive integers $p$ and $q$, knowing that such factorization with $|p-q|$ suitably small exists. Perhaps the most elementary method answering the question is trial division by integers starting at $\lfloor\sqrt n\rfloor$, going down. This succeeds after checking divisibility of $n$ by ...


8

I know an algorithm that runs in polynomial time would be able to break an RSA key pair "quickly". But how quickly is "quickly"? No way to say, it might be microseconds, and it might be large multiplies of the age of the universe. When we say that an algorithm runs in polynomial time, we're not saying anything about how fast the algorithm runs given ...


7

There is consensus that it is safe to use random primes $p$ and $q$ when generating 2048-bit (or wider) RSA public moduli which two prime factors $p$ and $q$ are about half the key size. That is sanctioned by FIPS 186-4, appendix B.3; specifically, wording in B.3.1 item A: Using methods 1 and 2 [yielding provable (1) and probable (2) random primes], ...


7

Short answer No, RSA encryption with a private key is not the same as RSA signature generation. RSA encryption can only be performed with an RSA public key according to the RSA standard. The terms Raw RSA or textbook RSA are often used to indicate RSA without a padding scheme. Raw RSA simply consists of modular exponentiation. Raw RSA is vulnerable to many ...


7

Yes, they are (deterministically) equivalent. The original RSA paper (Section IX.C), working off Miller's results (Theorem 3), showed how knowing the secret exponent $d$ was probabilistically equivalent to factoring $n$. Later, using more advanced techniques, Coron and May showed how to deterministically reduce finding $d$ to factoring $n$.


7

Think about this: what does it mean that $\gcd(e_B, e_C)=1$. Formally that means there exist some $s_1, s_2$ such that $e_Bs_1 + e_Cs_2=1$. Say you have two ciphertexts (the following math is all done modulo the shared modulus), $C_B=M^{e_B}$ and $C_C=M^{e_C}$. You can do the following: $$\begin{align} ...


7

There's no real difference between $p$ and $q$ in RSA. It looks like OpenSSL just has the agreement "$p$ has to be bigger than $q$" for conveniences. One of the numbers has to be bigger than the other (otherwise they would be the same number, and $p = q$ is very bad in RSA). Just use two examples: $p = 13$ and $q = 11$. $p$ is bigger than $q$, all right. ...


7

If $p$ and $q$ are 1024-bit primes, then by definition of the bit size of an integer (at least, a prime in a cryptographic context with glimpses of RSA), $2^{1023}\le p<2^{1024}$ and $2^{1023}\le q<2^{1024}$. Thus their product $n=pq$ verifies $2^{2046}\le n<2^{2048}$, and $n$ is a 2047-bit or 2048-bit integer. We show by exhibition that both cases ...


7

You are looking for Proxy Re-Encryption. From a high-level viewpoint, a proxy re-encryption scheme is an asymmetric encryption scheme that permits a proxy to transform ciphertexts under Alice's public key into ciphertexts decryptable by Bob's secret key. In order to do this, the delegator $A$ gives a special re-encryption key $rk_{A \rightarrow B}$ to the ...


7

Copy / paste that key into http://phpseclib.sourceforge.net/x509/asn1parse.php and you'll see that there are several different integers in there. p is there, q is there as is the exponent and several other integers to speed things up by taking advantage of the Chinese Remainder Theorem. The key is encoded using DER and derives semantic meaning via ASN.1. ...


6

This expands CodesInChaos's comment into an answer. Forward Secrecy (that is, maintaining confidentiality of messages enciphered before compromise of the long term key) can be achieved in a protocol using a public-key signature scheme with a long-term public key, and a public-key encryption scheme with a per-session key; but in the case of RSA signature and ...


6

A possible RSA variant uses: some odd exponent $e>2$ (that can be $e=3$ or $e=2^{16}+1$ as customary in standard RSA); $p$ and $q$ distinct large random primes, with $\gcd(e,p)=\gcd(e,p-1)=\gcd(e,q-1)=1$; $N=p^2\cdot q$; some $d$ computed such that $d\cdot e\equiv 1\pmod{\operatorname{lcm}(p,p-1,q-1)}$; public-key function $x\to x^e\bmod N$; private-key ...


6

ECDSA should in general create signatures faster than RSA for the same cryptographic strength if you just look at the mathematics. In the end the modular exponentiation is performed for smaller numbers. However, ECDSA depends on a random number generator, so ECDSA speeds may be slower if the random number generator blocks for any reason (and not using a good ...


6

BouncyCastle has a really bad ECC implementation. It uses affine coordinates which incur a huge performance hit (factor 20 or so) since it computes a field inversion after every single step. Good implementations use Jacobi coordinates (or a similar approach) where denominators are kept and there is only one field inversion at the end. It's also potentially ...


6

No, the RSA key size is not the size of the private key exponent. It is customarily the number of bits in the public modulus (which is known as $N$). In other words, the key size is the integer $k$ such that $2^{k-1}\le N<2^k$. In most implementations (and all implementations conforming to PKCS#1), a private exponent $d$ has size in bits at most the key ...


6

The only reason you are seeing this is because you are dealing with such small primes. With primes like we would use in practice (1024 bits), the probability of this happening is very, very small. And, it can only happen when $e>\sqrt{\lambda(n)}$. Since we typically use $e=65537$ in practice, it is guaranteed to not happen. Anyways, there is no mistake ...


6

To make it easier for humans to read.


6

I don't know about computing things in parallel, so I will ignore that part of the question. First, please note that the encryption algorithm is rarely the the weak point of the security. It is far more likely that you will have problems with the implementation, some spyware installed on your computer, a weak password (If you use qwerty as your password, ...


6

This describes some attacks against textbook RSA (also known as raw RSA), where the public or private functions $x\to y=x^e\bmod N$ or $y\to x=y^d\bmod N$ are applied directly to the message. Encryption / Decryption Determinism in textbook RSA allows an attacker - given a ciphertext - to search for the corresponding plaintext. Determinism also leads to ...


6

No, RSA encryption and signature is performed in (the multiplicative semigroup of) the factor ring $\mathbb Z/n\mathbb Z$ which is not a field since the non-zero elements $kp+n\mathbb Z$ (for $0<k<q$) and $kq+n\mathbb Z$ (for $0<k<p$) do not have multiplicative inverses. (However, one easily observes that all other non-zero elements are ...


6

Very important: Determining whether an integer is prime is significantly easier than factoring it (at least in the current state of our knowledge). We can easily determine whether integers having thousands of decimal digits are prime, but such integers are far beyond the reach of current factoring algorithms. Now to answer your question: "plain" RSA does ...


6

Definitions In RSA, an encryption key is a pair of integers $(N,e)$ with $N$ the product of $m\ge2$ distinct odds secret primes $r_i$ (with $0<i\le m$), and $e$ is such that $\gcd(e,\lambda(N))=1$ where $\lambda(N)=\operatorname{lcm}(r_1-1,\dots,r_m-1)$ is the Charmichael function. It follows that $e$ is odd. Typically, other conditions are added, like ...


5

Actually, the public exponent doesn't have to be prime; any odd number works just fine there. The most common public exponents (3, 17, 65537) all happen to be prime, but there's no requirement. Now, it turns out that a prime public exponent does make RSA key generation slightly easier in this respect; when you select primes $p$ and $q$, we need to make ...



Only top voted, non community-wiki answers of a minimum length are eligible