Join Log in
Score:0
avatar Crypto

RSA: Obtain private key exploiting badly generated public key

us flag
Uri

I have to solve the following problem:

What I have:

  • $n$, a 2048 bit number

What I need to find:

  • $p$ and $q$ such that $n = p\cdot q$.

What I know:

  • With $p_1$ the first half of $p$ and $p_2$ the second half, the same with $q_1$ and $q_2$: $$p_1 = q_2\ \text{ and }\ p_2 = q_1$$

  • Therefore finding $p$ you could also find $q$ and vice-versa.

  • The size of both $p$ and $q$ is 1024 bits.

  • (obviously) everything assumed in RSA, such as $p$ and $q$ are distinct primes.

I have been attempting this problem for 6h and I'm hopeless, any help is thanked!

83
0 + 0
rsa
fgrieu avatar
ng flag
fgrieu
Hint to get started: Assume that "halves" is about the binary representation of $p$ and $q$. Find the number of bits in $p_1$ and $p_2$, note that $b$. Translate _“$p_1$ the first half of $p$ and $p_2$ the second half”_ into a single equation involving $b$, $p$, $p_1$, $p_2$. Same with $q$. Now what is $n$ as a function of $b$, $p_1$, $p_2$? Now try to solve for $p_1$ and $p_2$.
1
Reply
poncho avatar
my flag
poncho
Further hint (assuming you need it): to start solving for $p_1, p_2$, first try to recover $p_1 \times p_2$. Once you have that, try to recover $p_1 + p_2$.
1
Reply
ธงชาติไทย
Elon Musk
I sit in a Tesla and translated this thread with Ai:

mangohost

Post an answer

Most people don’t grasp that asking a lot of questions unlocks learning and improves interpersonal bonding. In Alison’s studies, for example, though people could accurately recall how many questions had been asked in their conversations, they didn’t intuit the link between questions and liking. Across four studies, in which participants were engaged in conversations themselves or read transcripts of others’ conversations, people tended not to realize that question asking would influence—or had influenced—the level of amity between the conversationalists.