Impossible ElGamal signatures
up vote
0
down vote
favorite
From the following problem, I think it is not possible:
"
You find two signatures made by Alice. You know that she is
using the ElGamal signature scheme over $mathbb{F}_{2027}$. The cyclic group $mathbb{G}$ she is using is a
(multiplicative) subgroup of order 1013. The signatures are on hash values $h(m_1) =
345$ and $h(m_2) = 567$ and are given by $(r_1, s_1) = (365, 448)$ and $(r_2, s_2) = (365, 969)$.
Compute (a candidate for) Alice’s secret key $x$ based on these signatures, i.e. break
the system.
"
By the following equations, this is why I think these combinations are not possible:
$begin{cases} (365, 448) = (g^k mod 2027 , (345-365x)k^{-1} mod 2026) \
(365, 969) = (g^k mod 2027, (567-365x)k^{-1} mod 2026)
end{cases}$
The difference of the $y$-coordinate is $969-448 = 521mod 2026$ from the left side, and $(567-345)k^{-1}=222k^{-1} mod 2026$ from the right side. So the left side is odd and the right side is even while there are equal.
Do I do something wrong, or do you agree?
cryptography
asked Nov 15 at 15:46
Rocco van Vreumingen
478
|
show 6 more comments
up vote
0
down vote
favorite
From the following problem, I think it is not possible:
"
You find two signatures made by Alice. You know that she is
using the ElGamal signature scheme over $mathbb{F}_{2027}$. The cyclic group $mathbb{G}$ she is using is a
(multiplicative) subgroup of order 1013. The signatures are on hash values $h(m_1) =
345$ and $h(m_2) = 567$ and are given by $(r_1, s_1) = (365, 448)$ and $(r_2, s_2) = (365, 969)$.
Compute (a candidate for) Alice’s secret key $x$ based on these signatures, i.e. break
the system.
"
By the following equations, this is why I think these combinations are not possible:
$begin{cases} (365, 448) = (g^k mod 2027 , (345-365x)k^{-1} mod 2026) \
(365, 969) = (g^k mod 2027, (567-365x)k^{-1} mod 2026)
end{cases}$
The difference of the $y$-coordinate is $969-448 = 521mod 2026$ from the left side, and $(567-345)k^{-1}=222k^{-1} mod 2026$ from the right side. So the left side is odd and the right side is even while there are equal.
Do I do something wrong, or do you agree?
cryptography
asked Nov 15 at 15:46
Rocco van Vreumingen
478
even and odd are meaningless in modular arithmetic.
– Henno Brandsma
Nov 16 at 7:27
Why is that always meaningless?
– Rocco van Vreumingen
Nov 16 at 9:05
Not quite always, but e.g. modulo $9$ all $x$ are multiples of $2$. E.g. $7 = 2cdot 8$ in that ring.
– Henno Brandsma
Nov 16 at 9:05
Ok, but here we work with $mod (p-1)$ and $p-1$ is even. Hence $521 equiv 222k mod (p-1)$ is meaningless
– Rocco van Vreumingen
Nov 16 at 9:08
If $k$ works so does $k+1013$, as we work in a smaller group than the full $Z^ast_p$. One $k$ can be even, the other odd.
– Henno Brandsma
Nov 16 at 9:59
|
show 6 more comments
up vote
0
down vote
favorite
up vote
0
down vote
favorite
From the following problem, I think it is not possible:
"
You find two signatures made by Alice. You know that she is
using the ElGamal signature scheme over $mathbb{F}_{2027}$. The cyclic group $mathbb{G}$ she is using is a
(multiplicative) subgroup of order 1013. The signatures are on hash values $h(m_1) =
345$ and $h(m_2) = 567$ and are given by $(r_1, s_1) = (365, 448)$ and $(r_2, s_2) = (365, 969)$.
Compute (a candidate for) Alice’s secret key $x$ based on these signatures, i.e. break
the system.
"
By the following equations, this is why I think these combinations are not possible:
$begin{cases} (365, 448) = (g^k mod 2027 , (345-365x)k^{-1} mod 2026) \
(365, 969) = (g^k mod 2027, (567-365x)k^{-1} mod 2026)
end{cases}$
The difference of the $y$-coordinate is $969-448 = 521mod 2026$ from the left side, and $(567-345)k^{-1}=222k^{-1} mod 2026$ from the right side. So the left side is odd and the right side is even while there are equal.
Do I do something wrong, or do you agree?
cryptography
asked Nov 15 at 15:46
Rocco van Vreumingen
478
From the following problem, I think it is not possible:
"
You find two signatures made by Alice. You know that she is
using the ElGamal signature scheme over $mathbb{F}_{2027}$. The cyclic group $mathbb{G}$ she is using is a
(multiplicative) subgroup of order 1013. The signatures are on hash values $h(m_1) =
345$ and $h(m_2) = 567$ and are given by $(r_1, s_1) = (365, 448)$ and $(r_2, s_2) = (365, 969)$.
Compute (a candidate for) Alice’s secret key $x$ based on these signatures, i.e. break
the system.
"
By the following equations, this is why I think these combinations are not possible:
$begin{cases} (365, 448) = (g^k mod 2027 , (345-365x)k^{-1} mod 2026) \
(365, 969) = (g^k mod 2027, (567-365x)k^{-1} mod 2026)
end{cases}$
The difference of the $y$-coordinate is $969-448 = 521mod 2026$ from the left side, and $(567-345)k^{-1}=222k^{-1} mod 2026$ from the right side. So the left side is odd and the right side is even while there are equal.
Do I do something wrong, or do you agree?
cryptography
cryptography
asked Nov 15 at 15:46
Rocco van Vreumingen
478
asked Nov 15 at 15:46
Rocco van Vreumingen
478
asked Nov 15 at 15:46
Rocco van Vreumingen
478
asked Nov 15 at 15:46
Rocco van Vreumingen
478
asked Nov 15 at 15:46
Rocco van Vreumingen
478
478
even and odd are meaningless in modular arithmetic.
– Henno Brandsma
Nov 16 at 7:27
Why is that always meaningless?
– Rocco van Vreumingen
Nov 16 at 9:05
Not quite always, but e.g. modulo $9$ all $x$ are multiples of $2$. E.g. $7 = 2cdot 8$ in that ring.
– Henno Brandsma
Nov 16 at 9:05
Ok, but here we work with $mod (p-1)$ and $p-1$ is even. Hence $521 equiv 222k mod (p-1)$ is meaningless
– Rocco van Vreumingen
Nov 16 at 9:08
If $k$ works so does $k+1013$, as we work in a smaller group than the full $Z^ast_p$. One $k$ can be even, the other odd.
– Henno Brandsma
Nov 16 at 9:59
|
show 6 more comments
even and odd are meaningless in modular arithmetic.
– Henno Brandsma
Nov 16 at 7:27
Why is that always meaningless?
– Rocco van Vreumingen
Nov 16 at 9:05
Not quite always, but e.g. modulo $9$ all $x$ are multiples of $2$. E.g. $7 = 2cdot 8$ in that ring.
– Henno Brandsma
Nov 16 at 9:05
Ok, but here we work with $mod (p-1)$ and $p-1$ is even. Hence $521 equiv 222k mod (p-1)$ is meaningless
– Rocco van Vreumingen
Nov 16 at 9:08
If $k$ works so does $k+1013$, as we work in a smaller group than the full $Z^ast_p$. One $k$ can be even, the other odd.
– Henno Brandsma
Nov 16 at 9:59
even and odd are meaningless in modular arithmetic.
– Henno Brandsma
Nov 16 at 7:27
even and odd are meaningless in modular arithmetic.
– Henno Brandsma
Nov 16 at 7:27
Why is that always meaningless?
– Rocco van Vreumingen
Nov 16 at 9:05
Why is that always meaningless?
– Rocco van Vreumingen
Nov 16 at 9:05
Not quite always, but e.g. modulo $9$ all $x$ are multiples of $2$. E.g. $7 = 2cdot 8$ in that ring.
– Henno Brandsma
Nov 16 at 9:05
Not quite always, but e.g. modulo $9$ all $x$ are multiples of $2$. E.g. $7 = 2cdot 8$ in that ring.
– Henno Brandsma
Nov 16 at 9:05
Ok, but here we work with $mod (p-1)$ and $p-1$ is even. Hence $521 equiv 222k mod (p-1)$ is meaningless
– Rocco van Vreumingen
Nov 16 at 9:08
Ok, but here we work with $mod (p-1)$ and $p-1$ is even. Hence $521 equiv 222k mod (p-1)$ is meaningless
– Rocco van Vreumingen
Nov 16 at 9:08
If $k$ works so does $k+1013$, as we work in a smaller group than the full $Z^ast_p$. One $k$ can be even, the other odd.
– Henno Brandsma
Nov 16 at 9:59
If $k$ works so does $k+1013$, as we work in a smaller group than the full $Z^ast_p$. One $k$ can be even, the other odd.
– Henno Brandsma
Nov 16 at 9:59
|
show 6 more comments
1 Answer
1
active
oldest
votes
up vote
1
down vote
The verifying equations are
$$H(m) = xr + ks bmod{(p-1)}tag{1}$$
and
$$H(m') = xr + ks' bmod{(p-1)}tag{2}$$
and as we have a common $k$ and $r$, there are two unknowns $x$ and $k$.
Solve these equations by standard techniques, $H(m), H(m')$ are known and find $x$ (and $k$ too, but that's not very useful).
I did and found an $x$ that works. If $k$ works so does $k+1012$ as $g$ has order $1012$, and so these give the same $r$.
answered Nov 16 at 7:31
Henno Brandsma
102k344108
Yes, so $H(m) - H(m') equiv k(s-s')mod (p-1)$, but this yields $-521 equiv 222k mod (p-1)$, or equivalently $-521 - 222k equiv 0 mod (p-1)$. But since $-521-222k$ is odd and $p-1$ is even, is cannot be equal to a multiple of $p-1$. So it surprises me that you have found an $x$ and $k$.
– Rocco van Vreumingen
Nov 16 at 9:04
@RoccovanVreumingen I only computed the $x$ not the $k$.
– Henno Brandsma
Nov 16 at 9:09
$x = r^{-1}(s-s')^{-1}(sH(m')-s'H(m))$ and this I could compute modulo $p-1$.
– Henno Brandsma
Nov 16 at 9:10
It is clear how you found an $x$, but I still don't see what was wrong in my calculation.
– Rocco van Vreumingen
Nov 16 at 9:26
@RoccovanVreumingen the $k$ is determined mod 1013 only.
– Henno Brandsma
Nov 16 at 9:29
add a comment |
1 Answer
1
active
oldest
votes
1 Answer
1
active
oldest
votes
active
oldest
votes
active
oldest
votes
up vote
1
down vote
The verifying equations are
$$H(m) = xr + ks bmod{(p-1)}tag{1}$$
and
$$H(m') = xr + ks' bmod{(p-1)}tag{2}$$
and as we have a common $k$ and $r$, there are two unknowns $x$ and $k$.
Solve these equations by standard techniques, $H(m), H(m')$ are known and find $x$ (and $k$ too, but that's not very useful).
I did and found an $x$ that works. If $k$ works so does $k+1012$ as $g$ has order $1012$, and so these give the same $r$.
answered Nov 16 at 7:31
Henno Brandsma
102k344108
Yes, so $H(m) - H(m') equiv k(s-s')mod (p-1)$, but this yields $-521 equiv 222k mod (p-1)$, or equivalently $-521 - 222k equiv 0 mod (p-1)$. But since $-521-222k$ is odd and $p-1$ is even, is cannot be equal to a multiple of $p-1$. So it surprises me that you have found an $x$ and $k$.
– Rocco van Vreumingen
Nov 16 at 9:04
@RoccovanVreumingen I only computed the $x$ not the $k$.
– Henno Brandsma
Nov 16 at 9:09
$x = r^{-1}(s-s')^{-1}(sH(m')-s'H(m))$ and this I could compute modulo $p-1$.
– Henno Brandsma
Nov 16 at 9:10
It is clear how you found an $x$, but I still don't see what was wrong in my calculation.
– Rocco van Vreumingen
Nov 16 at 9:26
@RoccovanVreumingen the $k$ is determined mod 1013 only.
– Henno Brandsma
Nov 16 at 9:29
add a comment |
up vote
1
down vote
The verifying equations are
$$H(m) = xr + ks bmod{(p-1)}tag{1}$$
and
$$H(m') = xr + ks' bmod{(p-1)}tag{2}$$
and as we have a common $k$ and $r$, there are two unknowns $x$ and $k$.
Solve these equations by standard techniques, $H(m), H(m')$ are known and find $x$ (and $k$ too, but that's not very useful).
I did and found an $x$ that works. If $k$ works so does $k+1012$ as $g$ has order $1012$, and so these give the same $r$.
answered Nov 16 at 7:31
Henno Brandsma
102k344108
Yes, so $H(m) - H(m') equiv k(s-s')mod (p-1)$, but this yields $-521 equiv 222k mod (p-1)$, or equivalently $-521 - 222k equiv 0 mod (p-1)$. But since $-521-222k$ is odd and $p-1$ is even, is cannot be equal to a multiple of $p-1$. So it surprises me that you have found an $x$ and $k$.
– Rocco van Vreumingen
Nov 16 at 9:04
@RoccovanVreumingen I only computed the $x$ not the $k$.
– Henno Brandsma
Nov 16 at 9:09
$x = r^{-1}(s-s')^{-1}(sH(m')-s'H(m))$ and this I could compute modulo $p-1$.
– Henno Brandsma
Nov 16 at 9:10
It is clear how you found an $x$, but I still don't see what was wrong in my calculation.
– Rocco van Vreumingen
Nov 16 at 9:26
@RoccovanVreumingen the $k$ is determined mod 1013 only.
– Henno Brandsma
Nov 16 at 9:29
add a comment |
up vote
1
down vote
up vote
1
down vote
The verifying equations are
$$H(m) = xr + ks bmod{(p-1)}tag{1}$$
and
$$H(m') = xr + ks' bmod{(p-1)}tag{2}$$
and as we have a common $k$ and $r$, there are two unknowns $x$ and $k$.
Solve these equations by standard techniques, $H(m), H(m')$ are known and find $x$ (and $k$ too, but that's not very useful).
I did and found an $x$ that works. If $k$ works so does $k+1012$ as $g$ has order $1012$, and so these give the same $r$.
answered Nov 16 at 7:31
Henno Brandsma
102k344108
The verifying equations are
$$H(m) = xr + ks bmod{(p-1)}tag{1}$$
and
$$H(m') = xr + ks' bmod{(p-1)}tag{2}$$
and as we have a common $k$ and $r$, there are two unknowns $x$ and $k$.
Solve these equations by standard techniques, $H(m), H(m')$ are known and find $x$ (and $k$ too, but that's not very useful).
I did and found an $x$ that works. If $k$ works so does $k+1012$ as $g$ has order $1012$, and so these give the same $r$.
answered Nov 16 at 7:31
Henno Brandsma
102k344108
edited Nov 16 at 10:32
answered Nov 16 at 7:31
Henno Brandsma
102k344108
answered Nov 16 at 7:31
Henno Brandsma
102k344108
answered Nov 16 at 7:31
Henno Brandsma
102k344108
102k344108
Yes, so $H(m) - H(m') equiv k(s-s')mod (p-1)$, but this yields $-521 equiv 222k mod (p-1)$, or equivalently $-521 - 222k equiv 0 mod (p-1)$. But since $-521-222k$ is odd and $p-1$ is even, is cannot be equal to a multiple of $p-1$. So it surprises me that you have found an $x$ and $k$.
– Rocco van Vreumingen
Nov 16 at 9:04
@RoccovanVreumingen I only computed the $x$ not the $k$.
– Henno Brandsma
Nov 16 at 9:09
$x = r^{-1}(s-s')^{-1}(sH(m')-s'H(m))$ and this I could compute modulo $p-1$.
– Henno Brandsma
Nov 16 at 9:10
It is clear how you found an $x$, but I still don't see what was wrong in my calculation.
– Rocco van Vreumingen
Nov 16 at 9:26
@RoccovanVreumingen the $k$ is determined mod 1013 only.
– Henno Brandsma
Nov 16 at 9:29
add a comment |
Yes, so $H(m) - H(m') equiv k(s-s')mod (p-1)$, but this yields $-521 equiv 222k mod (p-1)$, or equivalently $-521 - 222k equiv 0 mod (p-1)$. But since $-521-222k$ is odd and $p-1$ is even, is cannot be equal to a multiple of $p-1$. So it surprises me that you have found an $x$ and $k$.
– Rocco van Vreumingen
Nov 16 at 9:04
@RoccovanVreumingen I only computed the $x$ not the $k$.
– Henno Brandsma
Nov 16 at 9:09
$x = r^{-1}(s-s')^{-1}(sH(m')-s'H(m))$ and this I could compute modulo $p-1$.
– Henno Brandsma
Nov 16 at 9:10
It is clear how you found an $x$, but I still don't see what was wrong in my calculation.
– Rocco van Vreumingen
Nov 16 at 9:26
@RoccovanVreumingen the $k$ is determined mod 1013 only.
– Henno Brandsma
Nov 16 at 9:29
Yes, so $H(m) - H(m') equiv k(s-s')mod (p-1)$, but this yields $-521 equiv 222k mod (p-1)$, or equivalently $-521 - 222k equiv 0 mod (p-1)$. But since $-521-222k$ is odd and $p-1$ is even, is cannot be equal to a multiple of $p-1$. So it surprises me that you have found an $x$ and $k$.
– Rocco van Vreumingen
Nov 16 at 9:04
Yes, so $H(m) - H(m') equiv k(s-s')mod (p-1)$, but this yields $-521 equiv 222k mod (p-1)$, or equivalently $-521 - 222k equiv 0 mod (p-1)$. But since $-521-222k$ is odd and $p-1$ is even, is cannot be equal to a multiple of $p-1$. So it surprises me that you have found an $x$ and $k$.
– Rocco van Vreumingen
Nov 16 at 9:04
@RoccovanVreumingen I only computed the $x$ not the $k$.
– Henno Brandsma
Nov 16 at 9:09
@RoccovanVreumingen I only computed the $x$ not the $k$.
– Henno Brandsma
Nov 16 at 9:09
$x = r^{-1}(s-s')^{-1}(sH(m')-s'H(m))$ and this I could compute modulo $p-1$.
– Henno Brandsma
Nov 16 at 9:10
$x = r^{-1}(s-s')^{-1}(sH(m')-s'H(m))$ and this I could compute modulo $p-1$.
– Henno Brandsma
Nov 16 at 9:10
It is clear how you found an $x$, but I still don't see what was wrong in my calculation.
– Rocco van Vreumingen
Nov 16 at 9:26
It is clear how you found an $x$, but I still don't see what was wrong in my calculation.
– Rocco van Vreumingen
Nov 16 at 9:26
@RoccovanVreumingen the $k$ is determined mod 1013 only.
– Henno Brandsma
Nov 16 at 9:29
@RoccovanVreumingen the $k$ is determined mod 1013 only.
– Henno Brandsma
Nov 16 at 9:29
add a comment |
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%2f2999857%2fimpossible-elgamal-signatures%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
even and odd are meaningless in modular arithmetic.
– Henno Brandsma
Nov 16 at 7:27
Why is that always meaningless?
– Rocco van Vreumingen
Nov 16 at 9:05
Not quite always, but e.g. modulo $9$ all $x$ are multiples of $2$. E.g. $7 = 2cdot 8$ in that ring.
– Henno Brandsma
Nov 16 at 9:05
Ok, but here we work with $mod (p-1)$ and $p-1$ is even. Hence $521 equiv 222k mod (p-1)$ is meaningless
– Rocco van Vreumingen
Nov 16 at 9:08
If $k$ works so does $k+1013$, as we work in a smaller group than the full $Z^ast_p$. One $k$ can be even, the other odd.
– Henno Brandsma
Nov 16 at 9:59