# Tag Info

6

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

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

4

$q$ does not divide $s^e-h(m)$, but $p$ does, so since the gcd must divide both $s^e-h(m)$ and $n$ it's $p$. To be even more explicit, we know that $p$ divides both $s^e-h(m)$ and $n$. The only larger divisor of $n$ that is also divisible by $p$ is $n$ itself, but if $n$ would divide $s^e-h(m)$, then $q$ would also divide $s^e-h(m)$, which we already assumed ...

3

Calculate $\phi(n) = (p-1) (q-1) = n - p - q + 1$. Then $d = e^{-1} \mod \phi(n)$. With OpenSSL, the code should look something like this (error checking omitted): BN_CTX *ctx = BN_ctx_new(); BIGNUM *d = BN_dup(n); BN_sub(d, d, p); BN_sub(d, d, q); BN_add_word(d, 1); BN_mod_inverse(d, e, n); BN_ctx_free(ctx); return d; The inverse calculation is less ...

3

512 bits (rounded down from the 664 bits or 200 digits in the patent) was recommended from its conception in 1974 and throughout the 1980s. Indeed, 463 bits was considered sufficient in the mid-1990s for the RSA-140 challenge. Whether key strengths as low as 100 digits (330 bits) were ever used in the early 1980s embedded systems is unclear; but probable ...

3

For part(a.ii), I am presuming that "enumerating candidate prime factors" means that we have a precomputed list of all 1536-bit primes, which we can simply test one at a time. To determine average running time we can use the prime number theorem, which states that the number of primes less that $N$ is approximately given by $\pi(x) \sim \frac{N}{\ln N}$. ...

2

Yes, this is doable. Here is a construction, built out of several basic primitives: Let $R$ be a randomized primality generation algorithm; there are many of them. It uses randomness, so let's make the bits of randomness it uses explicit as input: $R(c)$ is the output it produces, when given a random number generator that outputs the random bits $c$. ...

2

You never need larger parameters for RSA. In the worst case ElGamal parameters and RSA parameters are equal size. But you can significantly reduce ElGamal parameters depending on the setting you are using for ElGamal. If you are working in $Z_p$ for $p$ beging prime, you work in a field of the same bitlength as required for RSA. But to obtain IND-CPA ...

2

RSA and ElGammal are about equally secure at the same modulus size (assuming, of course, intelligent parameter selection in both cases). For RSA (assuming you use good padding), the best known-attack is to factor the modulus with NFS. For ElGammal (assuming you use a subgroup with a large enough prime factor), the best known-attack is to compute the ...

2

Check out the notes of paragraph 9.2 of that document, it lists all the encodings in hexadecimal values. It does so for PKCS#1 v1.5 padding for signature generation, but it certainly contains the OID's internally - 06 LL { OID } where LL species the length of the BER encoded OID: For the six hash functions mentioned in Appendix B.1, the DER ...

2

The question is from Problem 2 in Assignment 6 given here. It looks much like a straight instance of the RSA problem: we want to find $x\in\mathbb N$ such that $x^e=E\bmod R$ and $x<R$, given $R$, $E$, $e=7$, with $E$ expected to be the product of two unknown primes $p,q$ such that $e$ is coprime with $(p-1)\cdot(q-1)$. It is correct that knowing none of ...

2

DP is $d\bmod{p-1}$, similarly DQ is $d\bmod{q-1}$. InverseQ is $q^{-1}\bmod{p}$. These are used in applying the Chinese Remainder Theorem to RSA decryption, which is an optimization technique.

2

They rely on problems not so different as you might think. They are based either in the factoring problem or in the discrete logarithm problem, which have a deep connection between each other. Once you have an algorithm that can efficiently solve one, you most likely would be able to adapt it to reproduce an answer for the other in polynomial time. Thus ...

2

Hint: if $c_A$ is not invertible, what does that say about $gcd(c_A, n)$? How can you exploit that to obtain $m$ in another way?

2

First, note that if you know $p-q=a$ and $p+q=b$, for some $a,b$, you have two equations with two unknowns and can solve for $p,q$. Now, $$n=p*q=\left(\frac{p+q}{2}\right)^2 - \left(\frac{p-q}{2}\right)^2$$ Rearrange $$\left(\frac{p+q}{2}\right)^2 = n + \left(\frac{p-q}{2}\right)^2$$ Then start guessing values for $p-q$. Start with $2$ and substitute ...

2

The following potential reasons occur to me why someone might not choose to use the CRT optimization: The implementor worries about induced faults (but not quite enough to implement the obvious protection against it). That is, with the CRT optimization, we process the RSA block both mod p and mod q separately, and then combine them. That means that if ...

2

Using randomization on the RSA key before encryption doesn't work as easy as a simple XOR: the key (or actually, key pair) has some complicated mathematical structure, and the public part of it (the modulus and the public exponent) need to be known by the encrypting party. What might be possible would be to randomly chose the encryption exponent, and ...

1

The main problem here is that signature is malleable. Given signatures on $m_1$ and $m_2$ allows you to construct a valid signature on $m_1m_2$ by multiplying the signatures. Therefore, the answer is no. When you hash you don't have $H(m_1m_2)=H(m_1)H(m_2)$, so hashing destroys this algebraic structure that connects messages and signatures. EDIT: I'm ...

1

RSA CRT (with $N$ the product of two distinct primes $p$ and $q$) implements the $x\to y=x^d\bmod N$ private-key function by computing $y_p=x^d\bmod p$ and $y_q=x^d\bmod q$; then combining $y_p$ and $y_q$ into the desired $y$ by constructing the solution to the equations $y\equiv y_p\pmod p$, $y\equiv y_q\pmod q$, $0\le y<N$, with that last step requiring ...

1

I might be giving out too much information here (so don't read unless you want spoilers). Anyway, as rings the Chinese Remainder Theorem gives $$\mathbb{Z}/n\mathbb{Z} \cong \mathbb{Z}/p\mathbb{Z}\times \mathbb{Z}/q\mathbb{Z}$$ The isomorphism takes $(\mathbb{Z}/n\mathbb{Z})^\times$ to $(\mathbb{Z}/p\mathbb{Z})^\times \times ... 1 Hint: try to prove that$a^{phi(n)/g} \equiv 1 \pmod p$for all$a$satisfying$gcd(a, n) = 1$. Metahint:$phi(n)/g = (p-1) \times (q-1)/g$; is$(q-1)/g$an integer? 1 It is generally applied as far as I know. One thing that makes it tricky to implement in some situations is that it may be more vulnerable to certain side channel and fault injection attacks than "straight" RSA. Those attacks may expose the prime factors and thus the private key. I cannot see other reasons why it wouldn't be implementable on some platforms, ... 1 The notation you are seeing is for symmetric crypto. Garbled circuits typically use symmetric crypto since it can and symmetric crypto is fast. You may be able to do garbled circuits with asymmetric crypto, but it is definitely non-standard and may have subtle issues. 1 For$n$and$n'$RSA moduli of a size of practical interest (1024-bit and more) and correctly generated, we can say that the expected computing effort to factor both$n$and$n'$by any practical method that we know (including the best, which is GNFS) is about twice that to factor$n\$. How that translates to time is context-dependent. In particular, the ...

1

I have used the following python code to compute the private key and perform decryption. It uses the extended euclidean algorithm: def egcd(a, b): x,y, u,v = 0,1, 1,0 while a != 0: q, r = b//a, b%a m, n = x-u*q, y-v*q b,a, x,y, u,v = a,r, u,v, m,n gcd = b return gcd, x, y def main(): p = ...

1

Some observations, though I would recommend against inventing your own protocol, at least for real world use: When a new Chat group is formed, a random AES Key is generated and encrypted using each users public key. This means the protocol lacks forward secrecy. Anyone who compromises the private key of a chat participant can decrypt any previous chats ...

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