# Tag Info

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 ... 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 ... 16 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 ... 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)\\ ...

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 ...

12

From this answer: The difficulty of factoring (thus, as far as we know, the security of RSA in the absence of side-channel and padding attacks) grows smoothly with $n$. So, if factoring is the method of choice for breaking RSA, it doesn't seem like it really helps.

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 ...

11

The digital signature algorithm encrypts a hash using the senders private key and the receiver's public key. Huh? I see two problems with the above statement; "Encryption"; using the word encryption implies that there's a way somehow to decrypt it. However, there's no way to anyone, even with the private key, to "decrypt" a signature to generate the ...

11

I've been suggested to digitally sign it, thus, I have my private key, and I ship my application with a public key, and the application then uses the public key to check the QR code As long as you can live with the requirements for RSA (signature size, computation), that sounds like an excellent idea. Am I encrypting the whole message using the private ...

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 ...

10

There are many advantages of MAC's over signatures. For signatures you need to use asymmetric key pairs. Public keys need to be trusted for this to work. Unfortunately establishing trust is not that easy. Furthermore you don't want to use a private key stored on, for instance, a smart card (which would require a PIN and would likely be too slow). Instead ...

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 ...

9

Your problem is equivalent to solving $m^3 \equiv c \pmod n$. This corresponds to breaking RSA for $e=3$. We know no efficient way for doing that without factoring $n$. If you know the factors of $n$ you can compute the private exponent $d$ as $e \cdot d \equiv 1 \pmod{\varphi(n)}$ using the extended euclidean algorithm and then compute $m$ as $c^d$.

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 ...

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