RSA: Danger of using p to create qReducing key shares in Damgård-Dupont threshold RSAVerify a RSA signature using only RSA encryptionFinding Private Key $d$ using RSAInverting RSA using an oracleRSA encryption using multiplicationRSA encryption using euclidean alorithmBreaking RSA using Chinese Remainder TheoremManually encrypt using RSA X509 in .NETGenerate shared secrets using RSABreaking RSA using known root
What does 'script /dev/null' do?
Is Social Media Science Fiction?
New order #4: World
Ideas for 3rd eye abilities
Is there a name of the flying bionic bird?
Is it wise to focus on putting odd beats on left when playing double bass drums?
I see my dog run
Is "plugging out" electronic devices an American expression?
Was there ever an axiom rendered a theorem?
Patience, young "Padovan"
Copycat chess is back
Finding files for which a command fails
Does a dangling wire really electrocute me if I'm standing in water?
Calculate Levenshtein distance between two strings in Python
What is the command to reset a PC without deleting any files
Does the average primeness of natural numbers tend to zero?
Pristine Bit Checking
"My colleague's body is amazing"
What is the offset in a seaplane's hull?
How to answer pointed "are you quitting" questioning when I don't want them to suspect
What do the Banks children have against barley water?
Is domain driven design an anti-SQL pattern?
Symmetry in quantum mechanics
Unbreakable Formation vs. Cry of the Carnarium
RSA: Danger of using p to create q
Reducing key shares in Damgård-Dupont threshold RSAVerify a RSA signature using only RSA encryptionFinding Private Key $d$ using RSAInverting RSA using an oracleRSA encryption using multiplicationRSA encryption using euclidean alorithmBreaking RSA using Chinese Remainder TheoremManually encrypt using RSA X509 in .NETGenerate shared secrets using RSABreaking RSA using known root
$begingroup$
Assume my prime generation is as follows:
Pick a number $p$ between 1000 and 9999. $p=abcd$.
Make sure $p$ is prime
Construct $q$ such by taking the last 2 digits of $p$ and the first 2 digits of $p$, i.e. $q=cdab$
Make sure $q$ is prime.
Is the resulting $n = p·q$ more easily factorable?
My gut feeling says yes but I can't see why? I thought about Coppersmith but in this case, we don't have any common bit between $p$ and $q$ that are also at the same place. Is there a weakness?
rsa
edited 2 days ago
Paŭlo Ebermann
18.9k560106
asked Apr 5 at 17:00
S. L.S. L.
957
$endgroup$
add a comment |
$begingroup$
Assume my prime generation is as follows:
Pick a number $p$ between 1000 and 9999. $p=abcd$.
Make sure $p$ is prime
Construct $q$ such by taking the last 2 digits of $p$ and the first 2 digits of $p$, i.e. $q=cdab$
Make sure $q$ is prime.
Is the resulting $n = p·q$ more easily factorable?
My gut feeling says yes but I can't see why? I thought about Coppersmith but in this case, we don't have any common bit between $p$ and $q$ that are also at the same place. Is there a weakness?
rsa
edited 2 days ago
Paŭlo Ebermann
18.9k560106
asked Apr 5 at 17:00
S. L.S. L.
957
$endgroup$
2
$begingroup$
Of course, any product of two 4-digit primes is trivially factorable by trial division anyway, since there are only 1061 primes between 1000 and 9999. Add in the digit reversal requirement, and there are only 76(!) possible pairs to consider.
$endgroup$
– Ilmari Karonen
Apr 6 at 1:37
1
$begingroup$
@Nat: My fault, I added the "$= pq$" for context in an edit, and didn't notice the potential ambiguity. I see Paŭlo has already fixed it.
$endgroup$
– Ilmari Karonen
2 days ago
$begingroup$
I'd just like to add that this is inspired by a contest that just ended (12 minutes ago).
$endgroup$
– enedil
2 days ago
add a comment |
$begingroup$
Assume my prime generation is as follows:
Pick a number $p$ between 1000 and 9999. $p=abcd$.
Make sure $p$ is prime
Construct $q$ such by taking the last 2 digits of $p$ and the first 2 digits of $p$, i.e. $q=cdab$
Make sure $q$ is prime.
Is the resulting $n = p·q$ more easily factorable?
My gut feeling says yes but I can't see why? I thought about Coppersmith but in this case, we don't have any common bit between $p$ and $q$ that are also at the same place. Is there a weakness?
rsa
edited 2 days ago
Paŭlo Ebermann
18.9k560106
asked Apr 5 at 17:00
S. L.S. L.
957
$endgroup$
Assume my prime generation is as follows:
Pick a number $p$ between 1000 and 9999. $p=abcd$.
Make sure $p$ is prime
Construct $q$ such by taking the last 2 digits of $p$ and the first 2 digits of $p$, i.e. $q=cdab$
Make sure $q$ is prime.
Is the resulting $n = p·q$ more easily factorable?
My gut feeling says yes but I can't see why? I thought about Coppersmith but in this case, we don't have any common bit between $p$ and $q$ that are also at the same place. Is there a weakness?
rsa
rsa
edited 2 days ago
Paŭlo Ebermann
18.9k560106
asked Apr 5 at 17:00
S. L.S. L.
957
edited 2 days ago
Paŭlo Ebermann
18.9k560106
asked Apr 5 at 17:00
S. L.S. L.
957
edited 2 days ago
Paŭlo Ebermann
18.9k560106
edited 2 days ago
Paŭlo Ebermann
18.9k560106
edited 2 days ago
Paŭlo Ebermann
18.9k560106
18.9k560106
asked Apr 5 at 17:00
S. L.S. L.
957
asked Apr 5 at 17:00
S. L.S. L.
957
asked Apr 5 at 17:00
S. L.S. L.
957
957
2
$begingroup$
Of course, any product of two 4-digit primes is trivially factorable by trial division anyway, since there are only 1061 primes between 1000 and 9999. Add in the digit reversal requirement, and there are only 76(!) possible pairs to consider.
$endgroup$
– Ilmari Karonen
Apr 6 at 1:37
1
$begingroup$
@Nat: My fault, I added the "$= pq$" for context in an edit, and didn't notice the potential ambiguity. I see Paŭlo has already fixed it.
$endgroup$
– Ilmari Karonen
2 days ago
$begingroup$
I'd just like to add that this is inspired by a contest that just ended (12 minutes ago).
$endgroup$
– enedil
2 days ago
add a comment |
2
$begingroup$
Of course, any product of two 4-digit primes is trivially factorable by trial division anyway, since there are only 1061 primes between 1000 and 9999. Add in the digit reversal requirement, and there are only 76(!) possible pairs to consider.
$endgroup$
– Ilmari Karonen
Apr 6 at 1:37
1
$begingroup$
@Nat: My fault, I added the "$= pq$" for context in an edit, and didn't notice the potential ambiguity. I see Paŭlo has already fixed it.
$endgroup$
– Ilmari Karonen
2 days ago
$begingroup$
I'd just like to add that this is inspired by a contest that just ended (12 minutes ago).
$endgroup$
– enedil
2 days ago
2
2
$begingroup$
Of course, any product of two 4-digit primes is trivially factorable by trial division anyway, since there are only 1061 primes between 1000 and 9999. Add in the digit reversal requirement, and there are only 76(!) possible pairs to consider.
$endgroup$
– Ilmari Karonen
Apr 6 at 1:37
$begingroup$
Of course, any product of two 4-digit primes is trivially factorable by trial division anyway, since there are only 1061 primes between 1000 and 9999. Add in the digit reversal requirement, and there are only 76(!) possible pairs to consider.
$endgroup$
– Ilmari Karonen
Apr 6 at 1:37
1
1
$begingroup$
@Nat: My fault, I added the "$= pq$" for context in an edit, and didn't notice the potential ambiguity. I see Paŭlo has already fixed it.
$endgroup$
– Ilmari Karonen
2 days ago
$begingroup$
@Nat: My fault, I added the "$= pq$" for context in an edit, and didn't notice the potential ambiguity. I see Paŭlo has already fixed it.
$endgroup$
– Ilmari Karonen
2 days ago
$begingroup$
I'd just like to add that this is inspired by a contest that just ended (12 minutes ago).
$endgroup$
– enedil
2 days ago
$begingroup$
I'd just like to add that this is inspired by a contest that just ended (12 minutes ago).
$endgroup$
– enedil
2 days ago
add a comment |
2 Answers
2
active
oldest
votes
$begingroup$
You don't need anything fancy like Coppersmith, just simple algebra. The idea is to translate the equations we have involving the digits of $p$ and $q$ in base $B$ ($B = 100$ in your example) into equations involving the digits of $n$ in base $B$, which we know. You have $p = x B + y$ and $q = y B + x$, with $0 lt x, y lt B$. Then $n = x y B^2 + (x^2 + y^2) B + x y$.
The rightmost digit of $n$ in base $B$ is $(x y) bmod B$. Since $x,y le B-1$, $(x^2 + y^2) B + x y le 2 (B-1)^2 B + (B-1)^2 lt 2 (B-1)^2 (B+1) = 2 (B-1) (B^2-1) lt 2 B^3$. Hence the $B^3$ digit of $n$ is the $B$ digit of $x y$ plus $z$ where $0 le z lt 2$, i.e. $z in 0, 1$. So by reading the digits of $n$ in base $B$, we get the digits of $x y$ in base $B$, up to two possibilities, giving just two possibilities for $x y$ itself: $x y in W_0, W_1$.
Injecting this knowledge into the equation above gives us $x^2 + y^2 = (n - W_z (B^2 + 1)) / B$. And of course knowing both $x^2 + y^2$ and $x y$ gives $x$ and $y$.
answered Apr 5 at 17:27
GillesGilles
8,42232756
$endgroup$
$begingroup$
Thanks for the explanation! I get most of it but wouldn't $n= xyB^2 + Bx^2 + By^2 + xy$? Do the other equations hold?
$endgroup$
– S. L.
Apr 5 at 19:03
$begingroup$
@S.L. Woops, different equation, but same principle.
$endgroup$
– Gilles
Apr 5 at 20:39
add a comment |
$begingroup$
Here's how to recover $x, y$ in a way that's easier than factoring $n$ (I'll use the notation $x, y$ rather than your notation $ab, cd$):
We have $n = xyB^2 + (x^2+y^2)B + xy$
First, compute $n bmod B$, that gives you $xy bmod B$
Then, compute $lfloor (n - B^2(xy bmod B)) / B^3 rfloor$; this gives you $xy / B + epsilon$, where $0 le epsilon le 2$
Pasting those two together will give you a total of three possibilities of $xy$.
Then, for each possibility, compute $(n - xyB^2 - xy) / B + 2xy$ and $(n - xyB^2 - xy) / B - 2xy$; if the guess of $epsilon$ is correct, these will be $(x+y)^2$ and $(x-y)^2$; take squareroots, and extract $x, y$ directly.
(Thanks for Giles for pointing out this last part)
answered Apr 5 at 20:16
ponchoponcho
93.9k2146245
$endgroup$
$begingroup$
Yeah, right, the $B^3$ digit of $n$ gives the other digit of $x y$. And there's no need to factor anything: once you know $x y$, you know $x^2 + y^2$.
$endgroup$
– Gilles
Apr 5 at 20:39
$begingroup$
@Gilles: yup, you're right; I'll update the answer
$endgroup$
– poncho
Apr 5 at 21:01
$begingroup$
I don't get this part: Then, compute $⌊(n−B^2(xymod B))/B^3⌋$ this gives you $xy/B+ϵ$, where $0≤ϵ≤2$. I have $xymod B$ but not $xy$?
$endgroup$
– S. L.
Apr 5 at 21:10
1
$begingroup$
$(n - B^2(xy bmod B)) / B^3 = lfloor(xy/B) rfloor + x^2 / B^2 + y^2 / B^2 + xy / B^3$; we know that $x^2 / B^2, y^2 / B^2, xy / B^3$ are all less than 1 (and $ge 0$), and so the sum must be in the interval $[0, 3)$, that is, two or less once you round down...
$endgroup$
– poncho
Apr 5 at 22:18
add a comment |
Your Answer
StackExchange.ifUsing("editor", function ()
return StackExchange.using("mathjaxEditing", function ()
StackExchange.MarkdownEditor.creationCallbacks.add(function (editor, postfix)
StackExchange.mathjaxEditing.prepareWmdForMathJax(editor, postfix, [["$", "$"], ["\\(","\\)"]]);
);
);
, "mathjax-editing");
StackExchange.ready(function()
var channelOptions =
tags: "".split(" "),
id: "281"
;
initTagRenderer("".split(" "), "".split(" "), channelOptions);
StackExchange.using("externalEditor", function()
// Have to fire editor after snippets, if snippets enabled
if (StackExchange.settings.snippets.snippetsEnabled)
StackExchange.using("snippets", function()
createEditor();
);
else
createEditor();
);
function createEditor()
StackExchange.prepareEditor(
heartbeatType: 'answer',
autoActivateHeartbeat: false,
convertImagesToLinks: false,
noModals: true,
showLowRepImageUploadWarning: true,
reputationToPostImages: null,
bindNavPrevention: true,
postfix: "",
imageUploader:
brandingHtml: "Powered by u003ca class="icon-imgur-white" href="https://imgur.com/"u003eu003c/au003e",
contentPolicyHtml: "User contributions licensed under u003ca href="https://creativecommons.org/licenses/by-sa/3.0/"u003ecc by-sa 3.0 with attribution requiredu003c/au003e u003ca href="https://stackoverflow.com/legal/content-policy"u003e(content policy)u003c/au003e",
allowUrls: true
,
noCode: true, onDemand: true,
discardSelector: ".discard-answer"
,immediatelyShowMarkdownHelp:true
);
);
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
StackExchange.ready(
function ()
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fcrypto.stackexchange.com%2fquestions%2f68562%2frsa-danger-of-using-p-to-create-q%23new-answer', 'question_page');
);
Post as a guest
Required, but never shown
2 Answers
2
active
oldest
votes
2 Answers
2
active
oldest
votes
active
oldest
votes
active
oldest
votes
$begingroup$
You don't need anything fancy like Coppersmith, just simple algebra. The idea is to translate the equations we have involving the digits of $p$ and $q$ in base $B$ ($B = 100$ in your example) into equations involving the digits of $n$ in base $B$, which we know. You have $p = x B + y$ and $q = y B + x$, with $0 lt x, y lt B$. Then $n = x y B^2 + (x^2 + y^2) B + x y$.
The rightmost digit of $n$ in base $B$ is $(x y) bmod B$. Since $x,y le B-1$, $(x^2 + y^2) B + x y le 2 (B-1)^2 B + (B-1)^2 lt 2 (B-1)^2 (B+1) = 2 (B-1) (B^2-1) lt 2 B^3$. Hence the $B^3$ digit of $n$ is the $B$ digit of $x y$ plus $z$ where $0 le z lt 2$, i.e. $z in 0, 1$. So by reading the digits of $n$ in base $B$, we get the digits of $x y$ in base $B$, up to two possibilities, giving just two possibilities for $x y$ itself: $x y in W_0, W_1$.
Injecting this knowledge into the equation above gives us $x^2 + y^2 = (n - W_z (B^2 + 1)) / B$. And of course knowing both $x^2 + y^2$ and $x y$ gives $x$ and $y$.
answered Apr 5 at 17:27
GillesGilles
8,42232756
$endgroup$
$begingroup$
Thanks for the explanation! I get most of it but wouldn't $n= xyB^2 + Bx^2 + By^2 + xy$? Do the other equations hold?
$endgroup$
– S. L.
Apr 5 at 19:03
$begingroup$
@S.L. Woops, different equation, but same principle.
$endgroup$
– Gilles
Apr 5 at 20:39
add a comment |
$begingroup$
You don't need anything fancy like Coppersmith, just simple algebra. The idea is to translate the equations we have involving the digits of $p$ and $q$ in base $B$ ($B = 100$ in your example) into equations involving the digits of $n$ in base $B$, which we know. You have $p = x B + y$ and $q = y B + x$, with $0 lt x, y lt B$. Then $n = x y B^2 + (x^2 + y^2) B + x y$.
The rightmost digit of $n$ in base $B$ is $(x y) bmod B$. Since $x,y le B-1$, $(x^2 + y^2) B + x y le 2 (B-1)^2 B + (B-1)^2 lt 2 (B-1)^2 (B+1) = 2 (B-1) (B^2-1) lt 2 B^3$. Hence the $B^3$ digit of $n$ is the $B$ digit of $x y$ plus $z$ where $0 le z lt 2$, i.e. $z in 0, 1$. So by reading the digits of $n$ in base $B$, we get the digits of $x y$ in base $B$, up to two possibilities, giving just two possibilities for $x y$ itself: $x y in W_0, W_1$.
Injecting this knowledge into the equation above gives us $x^2 + y^2 = (n - W_z (B^2 + 1)) / B$. And of course knowing both $x^2 + y^2$ and $x y$ gives $x$ and $y$.
answered Apr 5 at 17:27
GillesGilles
8,42232756
$endgroup$
$begingroup$
Thanks for the explanation! I get most of it but wouldn't $n= xyB^2 + Bx^2 + By^2 + xy$? Do the other equations hold?
$endgroup$
– S. L.
Apr 5 at 19:03
$begingroup$
@S.L. Woops, different equation, but same principle.
$endgroup$
– Gilles
Apr 5 at 20:39
add a comment |
$begingroup$
You don't need anything fancy like Coppersmith, just simple algebra. The idea is to translate the equations we have involving the digits of $p$ and $q$ in base $B$ ($B = 100$ in your example) into equations involving the digits of $n$ in base $B$, which we know. You have $p = x B + y$ and $q = y B + x$, with $0 lt x, y lt B$. Then $n = x y B^2 + (x^2 + y^2) B + x y$.
The rightmost digit of $n$ in base $B$ is $(x y) bmod B$. Since $x,y le B-1$, $(x^2 + y^2) B + x y le 2 (B-1)^2 B + (B-1)^2 lt 2 (B-1)^2 (B+1) = 2 (B-1) (B^2-1) lt 2 B^3$. Hence the $B^3$ digit of $n$ is the $B$ digit of $x y$ plus $z$ where $0 le z lt 2$, i.e. $z in 0, 1$. So by reading the digits of $n$ in base $B$, we get the digits of $x y$ in base $B$, up to two possibilities, giving just two possibilities for $x y$ itself: $x y in W_0, W_1$.
Injecting this knowledge into the equation above gives us $x^2 + y^2 = (n - W_z (B^2 + 1)) / B$. And of course knowing both $x^2 + y^2$ and $x y$ gives $x$ and $y$.
answered Apr 5 at 17:27
GillesGilles
8,42232756
$endgroup$
You don't need anything fancy like Coppersmith, just simple algebra. The idea is to translate the equations we have involving the digits of $p$ and $q$ in base $B$ ($B = 100$ in your example) into equations involving the digits of $n$ in base $B$, which we know. You have $p = x B + y$ and $q = y B + x$, with $0 lt x, y lt B$. Then $n = x y B^2 + (x^2 + y^2) B + x y$.
The rightmost digit of $n$ in base $B$ is $(x y) bmod B$. Since $x,y le B-1$, $(x^2 + y^2) B + x y le 2 (B-1)^2 B + (B-1)^2 lt 2 (B-1)^2 (B+1) = 2 (B-1) (B^2-1) lt 2 B^3$. Hence the $B^3$ digit of $n$ is the $B$ digit of $x y$ plus $z$ where $0 le z lt 2$, i.e. $z in 0, 1$. So by reading the digits of $n$ in base $B$, we get the digits of $x y$ in base $B$, up to two possibilities, giving just two possibilities for $x y$ itself: $x y in W_0, W_1$.
Injecting this knowledge into the equation above gives us $x^2 + y^2 = (n - W_z (B^2 + 1)) / B$. And of course knowing both $x^2 + y^2$ and $x y$ gives $x$ and $y$.
answered Apr 5 at 17:27
GillesGilles
8,42232756
edited Apr 5 at 20:38
answered Apr 5 at 17:27
GillesGilles
8,42232756
answered Apr 5 at 17:27
GillesGilles
8,42232756
answered Apr 5 at 17:27
GillesGilles
8,42232756
8,42232756
$begingroup$
Thanks for the explanation! I get most of it but wouldn't $n= xyB^2 + Bx^2 + By^2 + xy$? Do the other equations hold?
$endgroup$
– S. L.
Apr 5 at 19:03
$begingroup$
@S.L. Woops, different equation, but same principle.
$endgroup$
– Gilles
Apr 5 at 20:39
add a comment |
$begingroup$
Thanks for the explanation! I get most of it but wouldn't $n= xyB^2 + Bx^2 + By^2 + xy$? Do the other equations hold?
$endgroup$
– S. L.
Apr 5 at 19:03
$begingroup$
@S.L. Woops, different equation, but same principle.
$endgroup$
– Gilles
Apr 5 at 20:39
$begingroup$
Thanks for the explanation! I get most of it but wouldn't $n= xyB^2 + Bx^2 + By^2 + xy$? Do the other equations hold?
$endgroup$
– S. L.
Apr 5 at 19:03
$begingroup$
Thanks for the explanation! I get most of it but wouldn't $n= xyB^2 + Bx^2 + By^2 + xy$? Do the other equations hold?
$endgroup$
– S. L.
Apr 5 at 19:03
$begingroup$
@S.L. Woops, different equation, but same principle.
$endgroup$
– Gilles
Apr 5 at 20:39
$begingroup$
@S.L. Woops, different equation, but same principle.
$endgroup$
– Gilles
Apr 5 at 20:39
add a comment |
$begingroup$
Here's how to recover $x, y$ in a way that's easier than factoring $n$ (I'll use the notation $x, y$ rather than your notation $ab, cd$):
We have $n = xyB^2 + (x^2+y^2)B + xy$
First, compute $n bmod B$, that gives you $xy bmod B$
Then, compute $lfloor (n - B^2(xy bmod B)) / B^3 rfloor$; this gives you $xy / B + epsilon$, where $0 le epsilon le 2$
Pasting those two together will give you a total of three possibilities of $xy$.
Then, for each possibility, compute $(n - xyB^2 - xy) / B + 2xy$ and $(n - xyB^2 - xy) / B - 2xy$; if the guess of $epsilon$ is correct, these will be $(x+y)^2$ and $(x-y)^2$; take squareroots, and extract $x, y$ directly.
(Thanks for Giles for pointing out this last part)
answered Apr 5 at 20:16
ponchoponcho
93.9k2146245
$endgroup$
$begingroup$
Yeah, right, the $B^3$ digit of $n$ gives the other digit of $x y$. And there's no need to factor anything: once you know $x y$, you know $x^2 + y^2$.
$endgroup$
– Gilles
Apr 5 at 20:39
$begingroup$
@Gilles: yup, you're right; I'll update the answer
$endgroup$
– poncho
Apr 5 at 21:01
$begingroup$
I don't get this part: Then, compute $⌊(n−B^2(xymod B))/B^3⌋$ this gives you $xy/B+ϵ$, where $0≤ϵ≤2$. I have $xymod B$ but not $xy$?
$endgroup$
– S. L.
Apr 5 at 21:10
1
$begingroup$
$(n - B^2(xy bmod B)) / B^3 = lfloor(xy/B) rfloor + x^2 / B^2 + y^2 / B^2 + xy / B^3$; we know that $x^2 / B^2, y^2 / B^2, xy / B^3$ are all less than 1 (and $ge 0$), and so the sum must be in the interval $[0, 3)$, that is, two or less once you round down...
$endgroup$
– poncho
Apr 5 at 22:18
add a comment |
$begingroup$
Here's how to recover $x, y$ in a way that's easier than factoring $n$ (I'll use the notation $x, y$ rather than your notation $ab, cd$):
We have $n = xyB^2 + (x^2+y^2)B + xy$
First, compute $n bmod B$, that gives you $xy bmod B$
Then, compute $lfloor (n - B^2(xy bmod B)) / B^3 rfloor$; this gives you $xy / B + epsilon$, where $0 le epsilon le 2$
Pasting those two together will give you a total of three possibilities of $xy$.
Then, for each possibility, compute $(n - xyB^2 - xy) / B + 2xy$ and $(n - xyB^2 - xy) / B - 2xy$; if the guess of $epsilon$ is correct, these will be $(x+y)^2$ and $(x-y)^2$; take squareroots, and extract $x, y$ directly.
(Thanks for Giles for pointing out this last part)
answered Apr 5 at 20:16
ponchoponcho
93.9k2146245
$endgroup$
$begingroup$
Yeah, right, the $B^3$ digit of $n$ gives the other digit of $x y$. And there's no need to factor anything: once you know $x y$, you know $x^2 + y^2$.
$endgroup$
– Gilles
Apr 5 at 20:39
$begingroup$
@Gilles: yup, you're right; I'll update the answer
$endgroup$
– poncho
Apr 5 at 21:01
$begingroup$
I don't get this part: Then, compute $⌊(n−B^2(xymod B))/B^3⌋$ this gives you $xy/B+ϵ$, where $0≤ϵ≤2$. I have $xymod B$ but not $xy$?
$endgroup$
– S. L.
Apr 5 at 21:10
1
$begingroup$
$(n - B^2(xy bmod B)) / B^3 = lfloor(xy/B) rfloor + x^2 / B^2 + y^2 / B^2 + xy / B^3$; we know that $x^2 / B^2, y^2 / B^2, xy / B^3$ are all less than 1 (and $ge 0$), and so the sum must be in the interval $[0, 3)$, that is, two or less once you round down...
$endgroup$
– poncho
Apr 5 at 22:18
add a comment |
$begingroup$
Here's how to recover $x, y$ in a way that's easier than factoring $n$ (I'll use the notation $x, y$ rather than your notation $ab, cd$):
We have $n = xyB^2 + (x^2+y^2)B + xy$
First, compute $n bmod B$, that gives you $xy bmod B$
Then, compute $lfloor (n - B^2(xy bmod B)) / B^3 rfloor$; this gives you $xy / B + epsilon$, where $0 le epsilon le 2$
Pasting those two together will give you a total of three possibilities of $xy$.
Then, for each possibility, compute $(n - xyB^2 - xy) / B + 2xy$ and $(n - xyB^2 - xy) / B - 2xy$; if the guess of $epsilon$ is correct, these will be $(x+y)^2$ and $(x-y)^2$; take squareroots, and extract $x, y$ directly.
(Thanks for Giles for pointing out this last part)
answered Apr 5 at 20:16
ponchoponcho
93.9k2146245
$endgroup$
Here's how to recover $x, y$ in a way that's easier than factoring $n$ (I'll use the notation $x, y$ rather than your notation $ab, cd$):
We have $n = xyB^2 + (x^2+y^2)B + xy$
First, compute $n bmod B$, that gives you $xy bmod B$
Then, compute $lfloor (n - B^2(xy bmod B)) / B^3 rfloor$; this gives you $xy / B + epsilon$, where $0 le epsilon le 2$
Pasting those two together will give you a total of three possibilities of $xy$.
Then, for each possibility, compute $(n - xyB^2 - xy) / B + 2xy$ and $(n - xyB^2 - xy) / B - 2xy$; if the guess of $epsilon$ is correct, these will be $(x+y)^2$ and $(x-y)^2$; take squareroots, and extract $x, y$ directly.
(Thanks for Giles for pointing out this last part)
answered Apr 5 at 20:16
ponchoponcho
93.9k2146245
edited Apr 5 at 21:07
answered Apr 5 at 20:16
ponchoponcho
93.9k2146245
answered Apr 5 at 20:16
ponchoponcho
93.9k2146245
answered Apr 5 at 20:16
ponchoponcho
93.9k2146245
93.9k2146245
$begingroup$
Yeah, right, the $B^3$ digit of $n$ gives the other digit of $x y$. And there's no need to factor anything: once you know $x y$, you know $x^2 + y^2$.
$endgroup$
– Gilles
Apr 5 at 20:39
$begingroup$
@Gilles: yup, you're right; I'll update the answer
$endgroup$
– poncho
Apr 5 at 21:01
$begingroup$
I don't get this part: Then, compute $⌊(n−B^2(xymod B))/B^3⌋$ this gives you $xy/B+ϵ$, where $0≤ϵ≤2$. I have $xymod B$ but not $xy$?
$endgroup$
– S. L.
Apr 5 at 21:10
1
$begingroup$
$(n - B^2(xy bmod B)) / B^3 = lfloor(xy/B) rfloor + x^2 / B^2 + y^2 / B^2 + xy / B^3$; we know that $x^2 / B^2, y^2 / B^2, xy / B^3$ are all less than 1 (and $ge 0$), and so the sum must be in the interval $[0, 3)$, that is, two or less once you round down...
$endgroup$
– poncho
Apr 5 at 22:18
add a comment |
$begingroup$
Yeah, right, the $B^3$ digit of $n$ gives the other digit of $x y$. And there's no need to factor anything: once you know $x y$, you know $x^2 + y^2$.
$endgroup$
– Gilles
Apr 5 at 20:39
$begingroup$
@Gilles: yup, you're right; I'll update the answer
$endgroup$
– poncho
Apr 5 at 21:01
$begingroup$
I don't get this part: Then, compute $⌊(n−B^2(xymod B))/B^3⌋$ this gives you $xy/B+ϵ$, where $0≤ϵ≤2$. I have $xymod B$ but not $xy$?
$endgroup$
– S. L.
Apr 5 at 21:10
1
$begingroup$
$(n - B^2(xy bmod B)) / B^3 = lfloor(xy/B) rfloor + x^2 / B^2 + y^2 / B^2 + xy / B^3$; we know that $x^2 / B^2, y^2 / B^2, xy / B^3$ are all less than 1 (and $ge 0$), and so the sum must be in the interval $[0, 3)$, that is, two or less once you round down...
$endgroup$
– poncho
Apr 5 at 22:18
$begingroup$
Yeah, right, the $B^3$ digit of $n$ gives the other digit of $x y$. And there's no need to factor anything: once you know $x y$, you know $x^2 + y^2$.
$endgroup$
– Gilles
Apr 5 at 20:39
$begingroup$
Yeah, right, the $B^3$ digit of $n$ gives the other digit of $x y$. And there's no need to factor anything: once you know $x y$, you know $x^2 + y^2$.
$endgroup$
– Gilles
Apr 5 at 20:39
$begingroup$
@Gilles: yup, you're right; I'll update the answer
$endgroup$
– poncho
Apr 5 at 21:01
$begingroup$
@Gilles: yup, you're right; I'll update the answer
$endgroup$
– poncho
Apr 5 at 21:01
$begingroup$
I don't get this part: Then, compute $⌊(n−B^2(xymod B))/B^3⌋$ this gives you $xy/B+ϵ$, where $0≤ϵ≤2$. I have $xymod B$ but not $xy$?
$endgroup$
– S. L.
Apr 5 at 21:10
$begingroup$
I don't get this part: Then, compute $⌊(n−B^2(xymod B))/B^3⌋$ this gives you $xy/B+ϵ$, where $0≤ϵ≤2$. I have $xymod B$ but not $xy$?
$endgroup$
– S. L.
Apr 5 at 21:10
1
1
$begingroup$
$(n - B^2(xy bmod B)) / B^3 = lfloor(xy/B) rfloor + x^2 / B^2 + y^2 / B^2 + xy / B^3$; we know that $x^2 / B^2, y^2 / B^2, xy / B^3$ are all less than 1 (and $ge 0$), and so the sum must be in the interval $[0, 3)$, that is, two or less once you round down...
$endgroup$
– poncho
Apr 5 at 22:18
$begingroup$
$(n - B^2(xy bmod B)) / B^3 = lfloor(xy/B) rfloor + x^2 / B^2 + y^2 / B^2 + xy / B^3$; we know that $x^2 / B^2, y^2 / B^2, xy / B^3$ are all less than 1 (and $ge 0$), and so the sum must be in the interval $[0, 3)$, that is, two or less once you round down...
$endgroup$
– poncho
Apr 5 at 22:18
add a comment |
Thanks for contributing an answer to Cryptography Stack Exchange!
- Please be sure to answer the question. Provide details and share your research!
But avoid …
- Asking for help, clarification, or responding to other answers.
- Making statements based on opinion; back them up with references or personal experience.
Use MathJax to format equations. MathJax reference.
To learn more, see our tips on writing great answers.
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
StackExchange.ready(
function ()
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fcrypto.stackexchange.com%2fquestions%2f68562%2frsa-danger-of-using-p-to-create-q%23new-answer', 'question_page');
);
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
2
$begingroup$
Of course, any product of two 4-digit primes is trivially factorable by trial division anyway, since there are only 1061 primes between 1000 and 9999. Add in the digit reversal requirement, and there are only 76(!) possible pairs to consider.
$endgroup$
– Ilmari Karonen
Apr 6 at 1:37
1
$begingroup$
@Nat: My fault, I added the "$= pq$" for context in an edit, and didn't notice the potential ambiguity. I see Paŭlo has already fixed it.
$endgroup$
– Ilmari Karonen
2 days ago
$begingroup$
I'd just like to add that this is inspired by a contest that just ended (12 minutes ago).
$endgroup$
– enedil
2 days ago