Hot answers tagged

49

Mental calculators do not have the result appearing in their brain by staring at the input. They follow some (broadly sequential) algorithm¹. And computers vastly outperform them when they use the same algorithm. That was already by at least a factor >100 for inexpensive personal computers in the late 1970s. For example, the record for 10 multiplications ...


20

Your thinking is against the common sense in cryptography and computing. And to be blunt, it's blatant pseudoscience. Human brains and the neurons within operate on scalar states. While it's arguable whether the brain process is deterministic or probabilistic, it does not possess the capability to create state superpositions like quantum computers could. ...


10

For human brains, it's all too easy to ignore the depth of the 2048+ bit figure. Let's do some engineering guesstimation exercise to illustrate. The original post by @derjack measures almost 700 characters long. Here's a 2048-bit number, written in 617 decimal digits (almost as long as the question): ...


5

I found a description of the format of the public key here posted by Victor from Blagoevgrad at GSMHosting.com. As mentioned in the comments, both signature sizes are also 2048 bits, so that's pretty conclusive. Here's the contents of the post of the information in the link: #define RSANUMBYTES 256 /* 2048 bit key length */ #define RSANUMWORDS (...


4

Given a 2048-bit RSA public key physically burned into hardware, is it feasible to find a keypair where the public key could be "overlaid"? The immediately obvious approach to attack this would be to search for a 2048 bit prime that overlays the modulus; by replacing the value with a prime, finding the private exponent is easy. And, in that range, ...


4

It's asked how, in RSA, one finds $e$ given $d$ and $N$. I'll ignore the question's requirement that $e$ is coprime with $N$, which is highly unusual and has no mathematical relevance. I'll also assume $p\ne q$, because it's necessary for the stated $\varphi(N)=(p-1)\cdot(q-1)$ to hold. With the question's definition of RSA, the method to find $e$ goes ...


4

Any human being who can factor 2048 bit numbers in their head faster than a computer is almost certainly a human being who has, in effect, discovered a new algorithm to factor numbers. Which, if implemented on a computer, would be even faster. But that doesn't rule this out. I'm going to be a bit less than totally precise below. For example, I'll mix up ...


3

Yes, it is even possible without interaction (nothing Bob needs to send to Alice). The method is called "ring signature". Let's say she wants to sign a message like "I am Alice an hereby proof to Bob that I know one of the keys". She hashes it to get $m$. Alice now generates a random value $r_i$ for every public key $k_i$ and encrypts ...


3

Just want to make sure that my understanding is correct whether there is only one public key for any private key, and vice versa. That is not correct; formally, for any valid private RSA key, there are an infinite number of public keys that will work with it, and for any valid public RSA key, there are an infinite number of private keys that will work with ...


2

Is it possible to retrieve the original message $m$ with this information? Well, this is a standard exercise for beginners (that is, you're supposed to learn from it), and so I won't spell out the answer. I will give you a hint: if you know $N, c_1 = m^a \bmod N, c_2 = m^b \bmod N$, can you compute the value of $c_3 = m^{a-b} \bmod N$? If so, how could you ...


2

The big picture In RSAES-OAEP, for a public modulus $n$ of $8k-7$ to $8k$ bits, a valid ciphertext $c$ is (among many other conditions) such that $(c^d\bmod n)\,<\,2^{8k-8}$. Manger's attack assumes that adversaries can send queries to a device intended for decryption, which performs that check (as it should), and somewhat leaks if this condition is met ...


2

Here is a proposal (out of my head). Big picture Bob draws a random $X$, and sends it deterministically enciphered under each public key Alice deciphers $X$ with the public key she holds Alice checks Bob did as expected given that $X$ Alice reveals $X$ to Bob More precisely: Define a $8b$-bit hash (say SHA-512) such that $\min(n_i)>2^{16b}$ Define a ...


2

The other answers have already correctly pointed out that animal brains are vastly slower and more error-prone than modern computers on all computational tasks except a select few that benefit a lot from the specific kind of pattern-recognition and planning skills that brains were evolved for. Obviously, this does not mean that an animal brain cannot be ...


2

You can use the extended Euclidean algorithm to calculate $d$. Quoting Wikipedia, given $a$ and $b$, the extended Euclidean algorithm gives you $x$ and $y$ such that $$ ax+by = \gcd{(a,b)}.$$ Since $e$ is prime, $\gcd{(e, \varphi(n))}=1$, so the algorithm gives you $x$ and $y$ with $$ex+\varphi(n)\cdot y=1$$ which means $$ex \equiv 1 \mod{\varphi(n)}$$ and ...


1

Presumably $d_p$ is the quantity $d \bmod (p-1) = e^{-1} \bmod (p-1)$, from which we get the core property $$ e\cdot d_p \equiv 1 \pmod{p-1}\,. $$ For a small $d_p$ we can easily, by bruteforce, find the quantity $e\cdot d_p -1 = k\cdot (p-1)$ for some large unknown integer $k$. Here we can take a hint from the Pollard $p-1$ factorization method—we have $2^{...


1

You are given $d \bmod(p−1)$.., the public exponent is $e=65537$. Is there some way to calculate $p$? Well, we know that $d_p = d \bmod p-1$ and $e$ are related by $d_p \cdot e = 1 + kp$, for some integer $k$, and that $k < 65537$ So, do a partial factorization of $d_p \cdot e - 1$ into $a \cdot b$, where $a$ consists of factors below 65537 and $b$ has ...


1

Fgrieu essentially gave the answer in comment, I will try to elaborate a bit in answer form. You can use extended euclidean algorithm to find d from e, but note the e you selected will not work. Because e is not co-prime with $\varphi(n)$ You need to select another one. For efficiency we usually like to select a small e with few set bits, usually of the form ...


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