Stack Exchange Network

Stack Exchange network consists of 175 Q&A communities including Stack Overflow, the largest, most trusted online community for developers to learn, share their knowledge, and build their careers.

Visit Stack Exchange

Hot answers tagged

15

RSA-768 took 2000 years of 2.2Ghz single core Opteron from year 2009 [1]. DJB et al wrote in 2013 [2] that RSA-1024 would take $2^{70}$ differences with $2^{24}$ per machine per second in 2009, so 2 million years. Hardware improved since then, and GNFS can use GPUs, so maybe better, but about a million years I guess. Absolutely the computation can be ...


7

You can't have two different public keys for the same RSA private key. That's just not how RSA works. Well, almost. There's a minor technical loophole, and it's the fact that RSA has equivalent keys. In particular, the public keys $(n, e)$ and $(n, e + \lambda(n))$ are equivalent, in the sense of producing the same ciphertext for the same (padded) ...


7

I'm one of the authors of the paper. In order to make the paper more approachable, we factored each major optimizations out into its own paper. There are three of these sub-papers, and they each stand on their own mostly independent of the others. "Approximate encoded permutations and piecewise quantum adders ". We put small amounts of padding at various ...


5

If an eavesdropper intercepts their conversation and gets the value of $c$ (namely, $m^e \bmod n$) and knows $e$ and $n$, could he not just brute-force different values of $m$ to see which works? Yes! This is part of why we do not use the function $x \mapsto x^e \bmod n$ to encrypt messages directly. Instead, a sensible sender will pick $x$ uniformly at ...


5

Since the input sizes are fixed, length-extension attacks are not relevant, so any of the SHA-2 functions reasonably implements the random oracle model assumed by OAEP or PSS via MGF1—even the default of SHA-1 works with MGF1. Obviously it will cost slightly more to use SHA-224 or SHA-384 than to use SHA-256 or SHA-512 because SHA-224 and SHA-384 are ...


3

Although PKCS1's ASN.1 is a quite common representation of RSA keys, it is not the only one used (and certainly not the only one possible). The standards for XML digital signature and encryption unsurprisingly use XML not ASN.1 for data structure: https://www.w3.org/TR/xmldsig-core1/#sec-RSAKeyValue The standards for JSON Web Signature and Encryption (...


3

Here's the problem: you have values $e, d, p$ that satisfy the relation: $$ed - 1 = k(p-1)$$ for some integer $k$; what you want to do is find some other prime $q$ (within some size range) that satisfies the relation: $$ed - 1 = k'(q-1)$$ (for some integer $k'$) Without this first relation, finding the second one would be difficult (as we would need to ...


3

$n - \phi(n) = p + q - 1$. $p$ and $q$ are secret uniform random 1024-bit prime numbers. Is a difference of near $2^{1024}$ ‘close’?


3

I should be able to safely encrypt and decrypt any number with bit lengths L < 513 (256+257) without losing information. Is this correct[?] No. The RSA operation $x \mapsto x^e \bmod n$ is unfit to ‘encrypt’ even short messages directly. Here is what you should do: Pick a hash function $H$ up front, like SHA-256 or SHAKE128, and bake it into your ...


2

In RSA with modulus $n$, the legitimate user's cost to encrypt a message is $(\log_2 n) (\log_2 \log_2 n)^{1 + o(1)}$ bit operations, with the best public exponent $e = 3$; and to decrypt a message (if you know the secret exponent) is $(\log_2 n) (\log_2 \log_2 n)^{2 + o(1)}$ bit operations. This is most assuredly not exponential in $n$ or even in the size $...


2

Suppose a signature is not an integer $s$ such that $s^e \equiv H(m) \pmod N$, but rather a pair of integers $(s, k)$ with $s < N$ and $k < N^{e - 1}$ such that $$s^e = H(m) + kN.$$ Then the verifier can verify this equation modulo a secret uniform random $v$-bit prime $r$, $$s^e \equiv H(m) + kN \pmod r.$$ There are $\pi(2^v) - \pi(2^{v-1})$ such ...


2

If you encrypt something with low entropy but use a fixed seed for OAEP, it is trivial to brute force it, and verify your guesses with public key, while randomized all or nothing padding will make verifying a guess impossible. In the context of signatures rather than encryption, it doesn't seem as severe, but you are supplying the attacker with a bunch of ...


1

If I understand correctly, you are looking for the integers $x$ such that, for all $b$, $x^b \equiv x \pmod n$. You almost have it! You've correctly identified $x = 0$ and $x = 1$ as solutions. If you had a solution $x$, what can you say about $x_i := x \bmod p_i$ for each $p_i$—how are $x_i$ and ${x_i}^b$ related modulo $p_i$? Can you use the solutions $...


1

The attacks on RSA and Elliptic curve cryptography(ECC) are based on Shor's quantum algorithm which is used for integer factorization in the context of RSA. Correction: Note that, as pointed out by @yyyyyyy in the comments, Shor's algorithm for DLP does not factor; neither is it based on finding the order of an element (which is usually known anyway in a ...


1

2466 digits for an RSA modulus is somewhat large, but not unseen. A larger RSA modulus, when it is properly sampled, can only lead to a better security guarantee. The ciphertext in RSA is $c = M^e \bmod n$, where $M$ is something derived from the input message $m$ - hence, it is perfectly normakl for $c$ to have the same bit length as $n$ (anything ...


1

In $\mathbb{Z}_p$ all points $c\neq 0,$ are invertible. Choosing any $c'\neq c$ will give you $c-c' \neq 0,$ thus it will be invertible.


1

Asymmetric algorithms Asymmetric algorithms rely on mathematical structure. Keys for asymmetric algorithms typically have some kind of structure, as opposed to being uniformly random bit strings. This structure can be exploited to reduce the cost of breaking the system. Additionally, with asymmetric cryptography, there is more information to work with; The ...


1

It might help to describe the padding arithmetically: first shift $p$ (the pin) $2048$ bits to the left, so compute $2^{2048}\cdot p$. To replace the trailing $0$'s by $1$'s we add $2^{2048}-1$. So given $p$ the message to be encrypted by the RSA function is $$m=2^k \cdot p + (2^k-1) = (p+1)\cdot 2^k - 1$$ with $k=2048$ and working in the ring $\mathbb{Z}...


1

As the padding is deterministic and the amount of input values is minimal, you can just try and encrypt each possible value with the public key. If the result - the ciphertext - is identical to the one you have then you've found the input value and therefore the PIN. You are guaranteed success in $2^{16}$ tries after all, that's 65536 tries in total.


1

A session key is used to share a symmetric key over asymmetric encryption. The reason behind this is that symmetric encryption algorithms are faster than asymmetric encryption algorithms, this is also called a hybrid cryptosystem, since it combines symmetric and asymmetric encryption. The session key is generated randomly at the start of a session and is ...


1

The OP asks two questions. The first question is: After we calculated $N = p * q$, we calculate $\varphi(N)$ and use it later to determine $e$ (PR) and $d$ (PU). But why? This is exactly the prescription on page 6 of the original RSA paper, where $n=p\cdot q$ is the product of two (very large) prime numbers, and, hence the number of integers relatively ...


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