Mixing
Cryptography RSA system
$begingroup$
I everyone,
I am considering an RSA encryption over the multiplicative group $G = (Z/nZ)$
of the ring $Z/nZ$, where $n = pq$, and $p$ and $q$ are distinct odd primes.
I assume that $H={x^4|xin G}$ is a subgroup of $G$.
Next, I am assuming that there comes a probabilistic polynomial-time algorithm $A$ that recovers a correct plaintext $m$ from any given ciphertext $c$ which belongs to the subgroup $H$ with nonnegligible probability. What kind of impact would the algorithm $A$ have on the security of the RSA encryption scheme over the group $G$, where $G$ is the same group as before?
by using Lagrange I have concluded that $|H|/|G|=frac{1}{16}$.
But how can I interpretate anything from that?
elementary-number-theory cryptography
edited Feb 3 at 8:10
Jyrki Lahtonen
110k13172392
asked Feb 3 at 7:14
Jonathan KierschJonathan Kiersch
1139
$endgroup$
add a comment |
$begingroup$
I everyone,
I am considering an RSA encryption over the multiplicative group $G = (Z/nZ)$
of the ring $Z/nZ$, where $n = pq$, and $p$ and $q$ are distinct odd primes.
I assume that $H={x^4|xin G}$ is a subgroup of $G$.
Next, I am assuming that there comes a probabilistic polynomial-time algorithm $A$ that recovers a correct plaintext $m$ from any given ciphertext $c$ which belongs to the subgroup $H$ with nonnegligible probability. What kind of impact would the algorithm $A$ have on the security of the RSA encryption scheme over the group $G$, where $G$ is the same group as before?
by using Lagrange I have concluded that $|H|/|G|=frac{1}{16}$.
But how can I interpretate anything from that?
elementary-number-theory cryptography
edited Feb 3 at 8:10
Jyrki Lahtonen
110k13172392
asked Feb 3 at 7:14
Jonathan KierschJonathan Kiersch
1139
$endgroup$
$begingroup$
$[G:H]=16$ only when both $p$ and $q$ are $equiv1pmod4$. If $pequiv3pmod4$ then all quadratic residues modulo $p$ are also fourth powers. In general $[G:H]$ can be any of $4,8$ or $16$.
$endgroup$
– Jyrki Lahtonen
Feb 3 at 7:20
$begingroup$
I don't capture how you derive that?
$endgroup$
– Jonathan Kiersch
Feb 3 at 7:33
$begingroup$
Assume that $p=4k+3$, and $xequiv a^2pmod p$. By Little Fermat $a^{4k+2}equiv1$, so $$xequiv a^2equiv a^2a^{4k+2}=a^{4(k+1)}=(a^{k+1})^4pmod p$$ is a fourth power as well.
$endgroup$
– Jyrki Lahtonen
Feb 3 at 8:08
$begingroup$
And an integer $hin H$ if and only if $h$ is a fourth power modulo both $p$ and $q$.
$endgroup$
– Jyrki Lahtonen
Feb 3 at 8:10
add a comment |
$begingroup$
I everyone,
I am considering an RSA encryption over the multiplicative group $G = (Z/nZ)$
of the ring $Z/nZ$, where $n = pq$, and $p$ and $q$ are distinct odd primes.
I assume that $H={x^4|xin G}$ is a subgroup of $G$.
Next, I am assuming that there comes a probabilistic polynomial-time algorithm $A$ that recovers a correct plaintext $m$ from any given ciphertext $c$ which belongs to the subgroup $H$ with nonnegligible probability. What kind of impact would the algorithm $A$ have on the security of the RSA encryption scheme over the group $G$, where $G$ is the same group as before?
by using Lagrange I have concluded that $|H|/|G|=frac{1}{16}$.
But how can I interpretate anything from that?
elementary-number-theory cryptography
edited Feb 3 at 8:10
Jyrki Lahtonen
110k13172392
asked Feb 3 at 7:14
Jonathan KierschJonathan Kiersch
1139
$endgroup$
I everyone,
I am considering an RSA encryption over the multiplicative group $G = (Z/nZ)$
of the ring $Z/nZ$, where $n = pq$, and $p$ and $q$ are distinct odd primes.
I assume that $H={x^4|xin G}$ is a subgroup of $G$.
Next, I am assuming that there comes a probabilistic polynomial-time algorithm $A$ that recovers a correct plaintext $m$ from any given ciphertext $c$ which belongs to the subgroup $H$ with nonnegligible probability. What kind of impact would the algorithm $A$ have on the security of the RSA encryption scheme over the group $G$, where $G$ is the same group as before?
by using Lagrange I have concluded that $|H|/|G|=frac{1}{16}$.
But how can I interpretate anything from that?
elementary-number-theory cryptography
elementary-number-theory cryptography
edited Feb 3 at 8:10
Jyrki Lahtonen
110k13172392
asked Feb 3 at 7:14
Jonathan KierschJonathan Kiersch
1139
edited Feb 3 at 8:10
Jyrki Lahtonen
110k13172392
asked Feb 3 at 7:14
Jonathan KierschJonathan Kiersch
1139
edited Feb 3 at 8:10
Jyrki Lahtonen
110k13172392
edited Feb 3 at 8:10
Jyrki Lahtonen
110k13172392
edited Feb 3 at 8:10
Jyrki Lahtonen
110k13172392
110k13172392
asked Feb 3 at 7:14
Jonathan KierschJonathan Kiersch
1139
asked Feb 3 at 7:14
Jonathan KierschJonathan Kiersch
1139
asked Feb 3 at 7:14
Jonathan KierschJonathan Kiersch
1139
1139
$begingroup$
$[G:H]=16$ only when both $p$ and $q$ are $equiv1pmod4$. If $pequiv3pmod4$ then all quadratic residues modulo $p$ are also fourth powers. In general $[G:H]$ can be any of $4,8$ or $16$.
$endgroup$
– Jyrki Lahtonen
Feb 3 at 7:20
$begingroup$
I don't capture how you derive that?
$endgroup$
– Jonathan Kiersch
Feb 3 at 7:33
$begingroup$
Assume that $p=4k+3$, and $xequiv a^2pmod p$. By Little Fermat $a^{4k+2}equiv1$, so $$xequiv a^2equiv a^2a^{4k+2}=a^{4(k+1)}=(a^{k+1})^4pmod p$$ is a fourth power as well.
$endgroup$
– Jyrki Lahtonen
Feb 3 at 8:08
$begingroup$
And an integer $hin H$ if and only if $h$ is a fourth power modulo both $p$ and $q$.
$endgroup$
– Jyrki Lahtonen
Feb 3 at 8:10
add a comment |
$begingroup$
$[G:H]=16$ only when both $p$ and $q$ are $equiv1pmod4$. If $pequiv3pmod4$ then all quadratic residues modulo $p$ are also fourth powers. In general $[G:H]$ can be any of $4,8$ or $16$.
$endgroup$
– Jyrki Lahtonen
Feb 3 at 7:20
$begingroup$
I don't capture how you derive that?
$endgroup$
– Jonathan Kiersch
Feb 3 at 7:33
$begingroup$
Assume that $p=4k+3$, and $xequiv a^2pmod p$. By Little Fermat $a^{4k+2}equiv1$, so $$xequiv a^2equiv a^2a^{4k+2}=a^{4(k+1)}=(a^{k+1})^4pmod p$$ is a fourth power as well.
$endgroup$
– Jyrki Lahtonen
Feb 3 at 8:08
$begingroup$
And an integer $hin H$ if and only if $h$ is a fourth power modulo both $p$ and $q$.
$endgroup$
– Jyrki Lahtonen
Feb 3 at 8:10
$begingroup$
$[G:H]=16$ only when both $p$ and $q$ are $equiv1pmod4$. If $pequiv3pmod4$ then all quadratic residues modulo $p$ are also fourth powers. In general $[G:H]$ can be any of $4,8$ or $16$.
$endgroup$
– Jyrki Lahtonen
Feb 3 at 7:20
$begingroup$
$[G:H]=16$ only when both $p$ and $q$ are $equiv1pmod4$. If $pequiv3pmod4$ then all quadratic residues modulo $p$ are also fourth powers. In general $[G:H]$ can be any of $4,8$ or $16$.
$endgroup$
– Jyrki Lahtonen
Feb 3 at 7:20
$begingroup$
I don't capture how you derive that?
$endgroup$
– Jonathan Kiersch
Feb 3 at 7:33
$begingroup$
I don't capture how you derive that?
$endgroup$
– Jonathan Kiersch
Feb 3 at 7:33
$begingroup$
Assume that $p=4k+3$, and $xequiv a^2pmod p$. By Little Fermat $a^{4k+2}equiv1$, so $$xequiv a^2equiv a^2a^{4k+2}=a^{4(k+1)}=(a^{k+1})^4pmod p$$ is a fourth power as well.
$endgroup$
– Jyrki Lahtonen
Feb 3 at 8:08
$begingroup$
Assume that $p=4k+3$, and $xequiv a^2pmod p$. By Little Fermat $a^{4k+2}equiv1$, so $$xequiv a^2equiv a^2a^{4k+2}=a^{4(k+1)}=(a^{k+1})^4pmod p$$ is a fourth power as well.
$endgroup$
– Jyrki Lahtonen
Feb 3 at 8:08
$begingroup$
And an integer $hin H$ if and only if $h$ is a fourth power modulo both $p$ and $q$.
$endgroup$
– Jyrki Lahtonen
Feb 3 at 8:10
$begingroup$
And an integer $hin H$ if and only if $h$ is a fourth power modulo both $p$ and $q$.
$endgroup$
– Jyrki Lahtonen
Feb 3 at 8:10
add a comment |
1 Answer
1
active
oldest
votes
$begingroup$
An almost (but not quite) complete idea. I first thought I had it, but I was too optimistic :-( This needs more work!
I think having an algorithm like $A$ would open the road for the following attack.
- Generate a "probable" set $D$ of representatives of cosets of the subgroup $H$. Observe that the index of $H$ in $G$ is at most sixteen, so $D$ is a reasonably small set. We may actually use a bigger set in place of $D$ as long as it is still reasonably small, and likely to contain a set of representatives of cosets of $H$.
- If $e$ is the public exponent, and $c$ is the given ciphertext, then one of $cell^{-e}$, $ellin D$ will be in the subgroup $H$. This is because $xH=ell H$
for one $ellin D$ (as per the wishful assumption). - So for each candidate $ellin D$ we try the algorithm $A$ with the input $cell^{-e}$. If successful we move to step 4. Otherwise try another $ell$.
- If $x$ is the plaintext corresponding to $cell^{-e}$. Then $x'=xell$ is the plaintext corresponding to $x$. In other words, you cracked $c$.
I am a bit uncertain about the best way of locating $D$. My first thought was to look for a prime numbers $ellequiv1pmod4$ such that $left(dfrac nellright)=-1$. Then either $left(dfrac pellright)=-1$ or $left(dfrac qellright)=-1$ and, by quadratic reciprocity, either $left(dfrac ell pright)=-1$ or $left(dfrac ell qright)=-1$. If we find enough such primes $ell_i, i=1,2,ldots,m,$ then it soon becomes likely that their cosets generate the group $G/H$. At that point the set of numbers $prod_{j=1}^mell_j^{a_j}, 0le a_j<4$ can serve in the role of $D$.
An even simpler (non-deterministic) possibility is to simply keep trying random numbers in the role of $ell$ in step 3.
answered Feb 3 at 8:00
Jyrki LahtonenJyrki Lahtonen
110k13172392
$endgroup$
$begingroup$
I see, but how could I say something about the impact of the algorithm (which is assumed to be a probabilistic polynmium) on the security of the RSA encryption? For step 3, when you say non-deterministic in the end, isn't that what I am assuming?
$endgroup$
– Jonathan Kiersch
Feb 3 at 8:11
$begingroup$
Yes. Guessing $ell$ (with at least $1/16$ chance of guessing correctly) simply adds another non-deterministic component. I initially hoped to find a set $D$ guaranteed to contain elements from each coset of $H$. But my thinking was flawed. Having a non-deterministic $A$ makes the whole attack non-deterministic anyway.
$endgroup$
– Jyrki Lahtonen
Feb 3 at 8:15
$begingroup$
Understood. I assume a_j denote bits? This was very helpful, thank you. Any chance you have time to help me with the problem in the link crypto.stackexchange.com/questions/66903/…
$endgroup$
– Jonathan Kiersch
Feb 3 at 8:26
add a comment |
Your Answer
StackExchange.ready(function() {
var channelOptions = {
tags: "".split(" "),
id: "69"
};
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: true,
noModals: true,
showLowRepImageUploadWarning: true,
reputationToPostImages: 10,
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%2fmath.stackexchange.com%2fquestions%2f3098288%2fcryptography-rsa-system%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
1 Answer
1
active
oldest
votes
1 Answer
1
active
oldest
votes
active
oldest
votes
active
oldest
votes
$begingroup$
An almost (but not quite) complete idea. I first thought I had it, but I was too optimistic :-( This needs more work!
I think having an algorithm like $A$ would open the road for the following attack.
- Generate a "probable" set $D$ of representatives of cosets of the subgroup $H$. Observe that the index of $H$ in $G$ is at most sixteen, so $D$ is a reasonably small set. We may actually use a bigger set in place of $D$ as long as it is still reasonably small, and likely to contain a set of representatives of cosets of $H$.
- If $e$ is the public exponent, and $c$ is the given ciphertext, then one of $cell^{-e}$, $ellin D$ will be in the subgroup $H$. This is because $xH=ell H$
for one $ellin D$ (as per the wishful assumption). - So for each candidate $ellin D$ we try the algorithm $A$ with the input $cell^{-e}$. If successful we move to step 4. Otherwise try another $ell$.
- If $x$ is the plaintext corresponding to $cell^{-e}$. Then $x'=xell$ is the plaintext corresponding to $x$. In other words, you cracked $c$.
I am a bit uncertain about the best way of locating $D$. My first thought was to look for a prime numbers $ellequiv1pmod4$ such that $left(dfrac nellright)=-1$. Then either $left(dfrac pellright)=-1$ or $left(dfrac qellright)=-1$ and, by quadratic reciprocity, either $left(dfrac ell pright)=-1$ or $left(dfrac ell qright)=-1$. If we find enough such primes $ell_i, i=1,2,ldots,m,$ then it soon becomes likely that their cosets generate the group $G/H$. At that point the set of numbers $prod_{j=1}^mell_j^{a_j}, 0le a_j<4$ can serve in the role of $D$.
An even simpler (non-deterministic) possibility is to simply keep trying random numbers in the role of $ell$ in step 3.
answered Feb 3 at 8:00
Jyrki LahtonenJyrki Lahtonen
110k13172392
$endgroup$
$begingroup$
I see, but how could I say something about the impact of the algorithm (which is assumed to be a probabilistic polynmium) on the security of the RSA encryption? For step 3, when you say non-deterministic in the end, isn't that what I am assuming?
$endgroup$
– Jonathan Kiersch
Feb 3 at 8:11
$begingroup$
Yes. Guessing $ell$ (with at least $1/16$ chance of guessing correctly) simply adds another non-deterministic component. I initially hoped to find a set $D$ guaranteed to contain elements from each coset of $H$. But my thinking was flawed. Having a non-deterministic $A$ makes the whole attack non-deterministic anyway.
$endgroup$
– Jyrki Lahtonen
Feb 3 at 8:15
$begingroup$
Understood. I assume a_j denote bits? This was very helpful, thank you. Any chance you have time to help me with the problem in the link crypto.stackexchange.com/questions/66903/…
$endgroup$
– Jonathan Kiersch
Feb 3 at 8:26
add a comment |
$begingroup$
An almost (but not quite) complete idea. I first thought I had it, but I was too optimistic :-( This needs more work!
I think having an algorithm like $A$ would open the road for the following attack.
- Generate a "probable" set $D$ of representatives of cosets of the subgroup $H$. Observe that the index of $H$ in $G$ is at most sixteen, so $D$ is a reasonably small set. We may actually use a bigger set in place of $D$ as long as it is still reasonably small, and likely to contain a set of representatives of cosets of $H$.
- If $e$ is the public exponent, and $c$ is the given ciphertext, then one of $cell^{-e}$, $ellin D$ will be in the subgroup $H$. This is because $xH=ell H$
for one $ellin D$ (as per the wishful assumption). - So for each candidate $ellin D$ we try the algorithm $A$ with the input $cell^{-e}$. If successful we move to step 4. Otherwise try another $ell$.
- If $x$ is the plaintext corresponding to $cell^{-e}$. Then $x'=xell$ is the plaintext corresponding to $x$. In other words, you cracked $c$.
I am a bit uncertain about the best way of locating $D$. My first thought was to look for a prime numbers $ellequiv1pmod4$ such that $left(dfrac nellright)=-1$. Then either $left(dfrac pellright)=-1$ or $left(dfrac qellright)=-1$ and, by quadratic reciprocity, either $left(dfrac ell pright)=-1$ or $left(dfrac ell qright)=-1$. If we find enough such primes $ell_i, i=1,2,ldots,m,$ then it soon becomes likely that their cosets generate the group $G/H$. At that point the set of numbers $prod_{j=1}^mell_j^{a_j}, 0le a_j<4$ can serve in the role of $D$.
An even simpler (non-deterministic) possibility is to simply keep trying random numbers in the role of $ell$ in step 3.
answered Feb 3 at 8:00
Jyrki LahtonenJyrki Lahtonen
110k13172392
$endgroup$
$begingroup$
I see, but how could I say something about the impact of the algorithm (which is assumed to be a probabilistic polynmium) on the security of the RSA encryption? For step 3, when you say non-deterministic in the end, isn't that what I am assuming?
$endgroup$
– Jonathan Kiersch
Feb 3 at 8:11
$begingroup$
Yes. Guessing $ell$ (with at least $1/16$ chance of guessing correctly) simply adds another non-deterministic component. I initially hoped to find a set $D$ guaranteed to contain elements from each coset of $H$. But my thinking was flawed. Having a non-deterministic $A$ makes the whole attack non-deterministic anyway.
$endgroup$
– Jyrki Lahtonen
Feb 3 at 8:15
$begingroup$
Understood. I assume a_j denote bits? This was very helpful, thank you. Any chance you have time to help me with the problem in the link crypto.stackexchange.com/questions/66903/…
$endgroup$
– Jonathan Kiersch
Feb 3 at 8:26
add a comment |
$begingroup$
An almost (but not quite) complete idea. I first thought I had it, but I was too optimistic :-( This needs more work!
I think having an algorithm like $A$ would open the road for the following attack.
- Generate a "probable" set $D$ of representatives of cosets of the subgroup $H$. Observe that the index of $H$ in $G$ is at most sixteen, so $D$ is a reasonably small set. We may actually use a bigger set in place of $D$ as long as it is still reasonably small, and likely to contain a set of representatives of cosets of $H$.
- If $e$ is the public exponent, and $c$ is the given ciphertext, then one of $cell^{-e}$, $ellin D$ will be in the subgroup $H$. This is because $xH=ell H$
for one $ellin D$ (as per the wishful assumption). - So for each candidate $ellin D$ we try the algorithm $A$ with the input $cell^{-e}$. If successful we move to step 4. Otherwise try another $ell$.
- If $x$ is the plaintext corresponding to $cell^{-e}$. Then $x'=xell$ is the plaintext corresponding to $x$. In other words, you cracked $c$.
I am a bit uncertain about the best way of locating $D$. My first thought was to look for a prime numbers $ellequiv1pmod4$ such that $left(dfrac nellright)=-1$. Then either $left(dfrac pellright)=-1$ or $left(dfrac qellright)=-1$ and, by quadratic reciprocity, either $left(dfrac ell pright)=-1$ or $left(dfrac ell qright)=-1$. If we find enough such primes $ell_i, i=1,2,ldots,m,$ then it soon becomes likely that their cosets generate the group $G/H$. At that point the set of numbers $prod_{j=1}^mell_j^{a_j}, 0le a_j<4$ can serve in the role of $D$.
An even simpler (non-deterministic) possibility is to simply keep trying random numbers in the role of $ell$ in step 3.
answered Feb 3 at 8:00
Jyrki LahtonenJyrki Lahtonen
110k13172392
$endgroup$
An almost (but not quite) complete idea. I first thought I had it, but I was too optimistic :-( This needs more work!
I think having an algorithm like $A$ would open the road for the following attack.
- Generate a "probable" set $D$ of representatives of cosets of the subgroup $H$. Observe that the index of $H$ in $G$ is at most sixteen, so $D$ is a reasonably small set. We may actually use a bigger set in place of $D$ as long as it is still reasonably small, and likely to contain a set of representatives of cosets of $H$.
- If $e$ is the public exponent, and $c$ is the given ciphertext, then one of $cell^{-e}$, $ellin D$ will be in the subgroup $H$. This is because $xH=ell H$
for one $ellin D$ (as per the wishful assumption). - So for each candidate $ellin D$ we try the algorithm $A$ with the input $cell^{-e}$. If successful we move to step 4. Otherwise try another $ell$.
- If $x$ is the plaintext corresponding to $cell^{-e}$. Then $x'=xell$ is the plaintext corresponding to $x$. In other words, you cracked $c$.
I am a bit uncertain about the best way of locating $D$. My first thought was to look for a prime numbers $ellequiv1pmod4$ such that $left(dfrac nellright)=-1$. Then either $left(dfrac pellright)=-1$ or $left(dfrac qellright)=-1$ and, by quadratic reciprocity, either $left(dfrac ell pright)=-1$ or $left(dfrac ell qright)=-1$. If we find enough such primes $ell_i, i=1,2,ldots,m,$ then it soon becomes likely that their cosets generate the group $G/H$. At that point the set of numbers $prod_{j=1}^mell_j^{a_j}, 0le a_j<4$ can serve in the role of $D$.
An even simpler (non-deterministic) possibility is to simply keep trying random numbers in the role of $ell$ in step 3.
answered Feb 3 at 8:00
Jyrki LahtonenJyrki Lahtonen
110k13172392
edited Feb 3 at 8:11
answered Feb 3 at 8:00
Jyrki LahtonenJyrki Lahtonen
110k13172392
answered Feb 3 at 8:00
Jyrki LahtonenJyrki Lahtonen
110k13172392
answered Feb 3 at 8:00
Jyrki LahtonenJyrki Lahtonen
110k13172392
110k13172392
$begingroup$
I see, but how could I say something about the impact of the algorithm (which is assumed to be a probabilistic polynmium) on the security of the RSA encryption? For step 3, when you say non-deterministic in the end, isn't that what I am assuming?
$endgroup$
– Jonathan Kiersch
Feb 3 at 8:11
$begingroup$
Yes. Guessing $ell$ (with at least $1/16$ chance of guessing correctly) simply adds another non-deterministic component. I initially hoped to find a set $D$ guaranteed to contain elements from each coset of $H$. But my thinking was flawed. Having a non-deterministic $A$ makes the whole attack non-deterministic anyway.
$endgroup$
– Jyrki Lahtonen
Feb 3 at 8:15
$begingroup$
Understood. I assume a_j denote bits? This was very helpful, thank you. Any chance you have time to help me with the problem in the link crypto.stackexchange.com/questions/66903/…
$endgroup$
– Jonathan Kiersch
Feb 3 at 8:26
add a comment |
$begingroup$
I see, but how could I say something about the impact of the algorithm (which is assumed to be a probabilistic polynmium) on the security of the RSA encryption? For step 3, when you say non-deterministic in the end, isn't that what I am assuming?
$endgroup$
– Jonathan Kiersch
Feb 3 at 8:11
$begingroup$
Yes. Guessing $ell$ (with at least $1/16$ chance of guessing correctly) simply adds another non-deterministic component. I initially hoped to find a set $D$ guaranteed to contain elements from each coset of $H$. But my thinking was flawed. Having a non-deterministic $A$ makes the whole attack non-deterministic anyway.
$endgroup$
– Jyrki Lahtonen
Feb 3 at 8:15
$begingroup$
Understood. I assume a_j denote bits? This was very helpful, thank you. Any chance you have time to help me with the problem in the link crypto.stackexchange.com/questions/66903/…
$endgroup$
– Jonathan Kiersch
Feb 3 at 8:26
$begingroup$
I see, but how could I say something about the impact of the algorithm (which is assumed to be a probabilistic polynmium) on the security of the RSA encryption? For step 3, when you say non-deterministic in the end, isn't that what I am assuming?
$endgroup$
– Jonathan Kiersch
Feb 3 at 8:11
$begingroup$
I see, but how could I say something about the impact of the algorithm (which is assumed to be a probabilistic polynmium) on the security of the RSA encryption? For step 3, when you say non-deterministic in the end, isn't that what I am assuming?
$endgroup$
– Jonathan Kiersch
Feb 3 at 8:11
$begingroup$
Yes. Guessing $ell$ (with at least $1/16$ chance of guessing correctly) simply adds another non-deterministic component. I initially hoped to find a set $D$ guaranteed to contain elements from each coset of $H$. But my thinking was flawed. Having a non-deterministic $A$ makes the whole attack non-deterministic anyway.
$endgroup$
– Jyrki Lahtonen
Feb 3 at 8:15
$begingroup$
Yes. Guessing $ell$ (with at least $1/16$ chance of guessing correctly) simply adds another non-deterministic component. I initially hoped to find a set $D$ guaranteed to contain elements from each coset of $H$. But my thinking was flawed. Having a non-deterministic $A$ makes the whole attack non-deterministic anyway.
$endgroup$
– Jyrki Lahtonen
Feb 3 at 8:15
$begingroup$
Understood. I assume a_j denote bits? This was very helpful, thank you. Any chance you have time to help me with the problem in the link crypto.stackexchange.com/questions/66903/…
$endgroup$
– Jonathan Kiersch
Feb 3 at 8:26
$begingroup$
Understood. I assume a_j denote bits? This was very helpful, thank you. Any chance you have time to help me with the problem in the link crypto.stackexchange.com/questions/66903/…
$endgroup$
– Jonathan Kiersch
Feb 3 at 8:26
add a comment |
Thanks for contributing an answer to Mathematics 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%2fmath.stackexchange.com%2fquestions%2f3098288%2fcryptography-rsa-system%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
$begingroup$
$[G:H]=16$ only when both $p$ and $q$ are $equiv1pmod4$. If $pequiv3pmod4$ then all quadratic residues modulo $p$ are also fourth powers. In general $[G:H]$ can be any of $4,8$ or $16$.
$endgroup$
– Jyrki Lahtonen
Feb 3 at 7:20
$begingroup$
I don't capture how you derive that?
$endgroup$
– Jonathan Kiersch
Feb 3 at 7:33
$begingroup$
Assume that $p=4k+3$, and $xequiv a^2pmod p$. By Little Fermat $a^{4k+2}equiv1$, so $$xequiv a^2equiv a^2a^{4k+2}=a^{4(k+1)}=(a^{k+1})^4pmod p$$ is a fourth power as well.
$endgroup$
– Jyrki Lahtonen
Feb 3 at 8:08
$begingroup$
And an integer $hin H$ if and only if $h$ is a fourth power modulo both $p$ and $q$.
$endgroup$
– Jyrki Lahtonen
Feb 3 at 8:10