Hot answers tagged

80

It (or rather, the software running on it) will use arbitrary-precision ("bignum") arithmetic. The way this works is basically the same way in which you (probably) learned to do arithmetic on paper at school. The arithmetic taught to us humans at school is base-10 arithmetic — that is, we represent numbers as strings made up of ten different digits, ...


70

An ASN.1-encoded SSH private key contains the following integers in order: The public modulus $n$ and exponent $e$; The private exponent $d$; The prime factors $p$ and $q$ of $n$; The "reduced" private exponents $d_p=d\bmod(p-1)$ and $d_q=d\bmod(q-1)$; The "CRT coefficient" $q_{\text{inv}}=q^{-1}\bmod p$. The observation that the value of $d$ in such a ...


54

First, you do not break RSA through brute force. RSA is an asymmetric encryption algorithm, with a public/private key pair. The public key has a strong internal structure, and unravelling it yields access to the private key (basically, the main component of the public key is the modulus, which is a big composite integer, and the private key is equivalent to ...


38

Surprisingly, very basic algorithms which the children learn at the basic schools are used. For instance: http://www.wikihow.com/Do-Long-Multiplication You can find a similar algorithm for sum, sub and division. Try to ask google for: "division on paper" The "power of" is little tricky. In cryptography you don't really need the "real power of". Instead ...


34

The answer is in the source, file sshrsag.c, line 9: #define RSA_EXPONENT 37 /* we like this prime */ This value $e=37$ matches the conditions for a reasonable fixed RSA public exponent: $e$ is odd, $e$ is at least $3$, $e$ is reasonably small. The later condition is good for speed of operations involving the public key (encryption, ...


29

There are two reasons by which such "huge" numbers can be computed in reasonable time. The first one is that we do not raise one integer x to some big exponent d. What we do is that we compute x raised to power d modulo an integer n. The modulo means that we are not interested in the final integer xd but only in the remainder of the Euclidian division of xd ...


19

Actually, if you're willing to consider a somewhat larger $e$, I found a solution that makes the decryption part real cheap. This solution has $e = 446185741$ and $n = 3*5*7*11*13*23*29*31*43*47*53*61*67*71*79*103*131*139*157*191*211*229*239*277*331*419*421*443*461*463*547*571*599*647*661*691*859*911*967*1013*1021*1093*1123*1327*1381*1429*1483*1597*1871*...


19

A couple things: This article is two years old, so take its predictions with a grain of salt. In the two years that have elapsed, the predicted advances have not materialized, and there is little indication they will soon. The core of those arguments was Joux's 2013 result on the discrete logarithm problem in finite fields of small characteristic. Those ...


18

This question has many problems in the way it was asked, and clearly did not come after doing some investigation. However, since this seems to be a misconception that is spreading widely, I will relate to it. It is not true that the "crypto community" (whoever that is) believes that the NSA can break RSA. In fact, if Snowden taught us anything, it is that ...


17

This is a common mistake, so I'd like to give an in-depth answer. Basically, what you are proposing is to rely on the ONE-WAYNESS of RSA as a ONE-WAY FUNCTION, rather than relying on its CPA or CCA security as an encryption scheme. The advantage of using RSA as a one-way function is that no padding etc is needed. Now, the first important thing to note is ...


16

Suppose an RSA public key is still $(e, N)$ and the private key is still $d$. We have $Enc = (m*e) \text{ mod } N$ and $Dec = (c*d) \text{ mod } N$. The correctness of the scheme depends on the fact that $Dec(Enc(m)) = (m*e*d) \text{ mod } N = m \text{ mod } N$. This implies $e*d = 1 \text{ mod } N$. It is thus trivial to compute the private key given only ...


15

If we want to compact an existing RSA private key expressed as $(N,e,d,p,q,d_p,d_q,q_\text{inv})$, we can reduce it to $(e,p,q)$ and easily recompute the rest as: $\begin{align} N&=p\cdot q\\ d&=e^{-1}\bmod\operatorname{lcm}(p-1,q-1)\;\text{ or }\;d=e^{-1}\bmod((p-1)\cdot(q-1))\\ d_p&=d\bmod(p-1)\;\text{ or equivalently }\;d_p=e^{-1}\bmod(p-1)\\ ...


15

However, factoring a large integer is extremely difficult, even for a computer using known factoring algorithms. Not categorically. Factoring a large integer is trivial if it is only composed of small factors. A fairly naive algorithm for factoring N is the following: while N > 1: for p in increasing_primes: while p divides N: N = N / p ...


14

Any $e$ such that $\gcd(e, (p-1)(q-1)) = 1$ will do. There is no need for it to be in the set $\{3,17,65537\}$; these last numbers are chosen for speed of encryption, mostly (two set bits leads to faster computation of modular exponentation), and these numbers happen to be prime, so the condition is easily checked. One often encounters other $e$, but many ...


14

The main reasons we usually choose $p$ an $q$ prime numbers are: For a given size of $N=pq$, that makes $N$ harder to factor, hence RSA safer. Although efficient factoring algorithms do not find factors by trial division, it remains much easier to find very small prime factors than large ones. If we chose $p$ and/or $q$ at random without consideration for ...


13

Actually, if the RSA key generation is malicious, there are even more subtle ways that can someone can leak the key. The cleverest way I've seen works like this (assuming that we're generating an RSA-1024 key; for RSA-2048, we just use a larger curve): The attacker generates an EC public/private key pair; using a 192 bit curve for RSA-1024 is good. He ...


12

You can use a seed to start a PRNG. Then you can use that PRNG to generate the two (or more) primes required to generate the key pair. Now if you save that seed you can regenerate the key pair, which means you don't have the store the modulus, CRT components or private exponent. So yes, it is possible to reduce the size, but this approach does have ...


11

RSA moduli are generally of the form $N = pq$ for two primes $p$ and $q$. It is also important that $p$ and $q$ have (roughly) the same size. The main reason is that the security of RSA is related to the factoring problem. The most difficult numbers to factor are numbers that are the product of two primes of similar size. Note. There are basically two ...


10

Why can the public key exponent not be negative? Technically, it can be. There's just no point to using such negative exponents in general, since for every valid negative RSA exponent, there is an equivalent positive one that is easier to calculate with. Specifically, for any exponent $e$, message $m$ and modulus $n = pq$, changing $e$ by any integer ...


10

Hash functions must be public, so if you want use RSA as hash function you should fix $K$. Now let $n$ be the RSA module and $H$ denote RSA hash function. We have $$H(M)=H(M+n)$$ so this function is not second preimage and collision resistant. Also this system is not first preimage resistant (with known public and private key): Let $M^k=h \pmod n$ ...


10

There are three use cases where RSA beats common ECC algorithms, such as ECDSA: Signature with verification frequent or/and by low-power devices. The verification cost of $n$-bit RSA with usual public exponents is $O(n^2)$, but the verification cost of ECC-based signatures is $O(n^3)$ (using usual algorithms). Together with simpler math, that's why RSA can ...


9

An option strictly matching the question's statement (which requires $e=65537$) is to choose the public modulus $n$ as the product of many small primes $p_i$, perhaps $k=64$ primes of $32$ bits. That's multiprime RSA pushed to the max. The potential speedup is considerable. For small $k$, and standard arithmetic (quadratic multiplication and modular ...


9

Yes you can use Big-O notation to express runtime, that's customary. Formally, that does not give an upper bound on runtime for any fixed parameters, much less a lower bound; formally, that gives you an indication of how an upper bound would behave when some parameter grows to infinity, and no practical indication. However, in practice, when dealing with ...


9

If your calculator is able to compute $n^2$, you can compute $m^e \bmod n$ using the binary exponential method. In this method, you should first compute the binary form of $e$. Let $\ell$ be the number of bits in $e$, and let $e_i$ denote the $i$-th bit of $e$, so that $e=\sum\limits_{i=0}^\ell e_i \cdot 2^i$. Now, with the algorithm below, you can compute ...


9

If $e$ is a random number, then knowledge of the factorization allows us to reduce the recovery operation to: $$(c \bmod p) = (m \bmod p)^{e \bmod p-1} \pmod p$$ $$(c \bmod q) = (m \bmod q)^{e \bmod q-1} \pmod q$$ Solving both these discrete log problems will give us enough information on $e$ to efficiently recover it. Now, while solving these two ...


8

The use of the AES key many times is not a problem. However, there is a fundamental flaw with your solution. The server has no way of validating that it received the client's authentic public key. In particular, a man-in-the-middle can capture the client's public key, can forward its own public key to the server, and can then decrypt all traffic sent by each ...


8

You are looking at the ASN.1 encoding of private (and public) keys; the 00 values you see are an artifact of how ASN.1 encodes integers. ASN.1 is a method for describing data structures, and has ways to represents all sorts of data types. It wasn't designed with public keys (or cryptography) in mind; it was intended for more general use, initially ...


8

There is likely an assumption on the sizes of $p$ and $q$ that you haven't listed in your question that exists in the description. For example, Boneh's description of Wiener's attack has that $q<p<2q$. With that assumption, we can prove the inequality. We know that $$p+q < 2q+q$$ $$p+q < 3q$$ Furthermore, since $N=pq$ and $p>q$, we have ...


8

No, the security is about identical, as the underlying RSA problem is the same. Besides that, non-repudiation is usually managed differently with regards to legal requirements. Providing confidentiality (encryption) is a rather different use case than non-repudiation (signing a contract). It is also possible to use signatures for authentication rather than ...


8

Assumption: $e$ and $d$ are prime with $N$. If we use the multiplication instead of the power. We have $d \equiv e^{-1} \pmod N$ : \begin{align}c \times d &= m &\mod N\\ m \times e \times d &= m &\mod N\\ e \times d &= 1 &\mod N \end{align} (It has to work for any $m$ so we can suppose $m$ prime). $e$ and $N$ are publicly known, to ...



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