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 2 days ago
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 2 days ago
Rocco van Vreumingen
478
even and odd are meaningless in modular arithmetic.
– Henno Brandsma
yesterday
Why is that always meaningless?
– Rocco van Vreumingen
yesterday
Not quite always, but e.g. modulo $9$ all $x$ are multiples of $2$. E.g. $7 = 2cdot 8$ in that ring.
– Henno Brandsma
yesterday
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
yesterday
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
yesterday
|
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 2 days ago
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 2 days ago
Rocco van Vreumingen
478
asked 2 days ago
Rocco van Vreumingen
478
asked 2 days ago
Rocco van Vreumingen
478
asked 2 days ago
Rocco van Vreumingen
478
asked 2 days ago
Rocco van Vreumingen
478
478
even and odd are meaningless in modular arithmetic.
– Henno Brandsma
yesterday
Why is that always meaningless?
– Rocco van Vreumingen
yesterday
Not quite always, but e.g. modulo $9$ all $x$ are multiples of $2$. E.g. $7 = 2cdot 8$ in that ring.
– Henno Brandsma
yesterday
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
yesterday
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
yesterday
|
show 6 more comments
even and odd are meaningless in modular arithmetic.
– Henno Brandsma
yesterday
Why is that always meaningless?
– Rocco van Vreumingen
yesterday
Not quite always, but e.g. modulo $9$ all $x$ are multiples of $2$. E.g. $7 = 2cdot 8$ in that ring.
– Henno Brandsma
yesterday
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
yesterday
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
yesterday
even and odd are meaningless in modular arithmetic.
– Henno Brandsma
yesterday
even and odd are meaningless in modular arithmetic.
– Henno Brandsma
yesterday
Why is that always meaningless?
– Rocco van Vreumingen
yesterday
Why is that always meaningless?
– Rocco van Vreumingen
yesterday
Not quite always, but e.g. modulo $9$ all $x$ are multiples of $2$. E.g. $7 = 2cdot 8$ in that ring.
– Henno Brandsma
yesterday
Not quite always, but e.g. modulo $9$ all $x$ are multiples of $2$. E.g. $7 = 2cdot 8$ in that ring.
– Henno Brandsma
yesterday
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
yesterday
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
yesterday
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
yesterday
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
yesterday
|
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 yesterday
Henno Brandsma
101k344107
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
yesterday
@RoccovanVreumingen I only computed the $x$ not the $k$.
– Henno Brandsma
yesterday
$x = r^{-1}(s-s')^{-1}(sH(m')-s'H(m))$ and this I could compute modulo $p-1$.
– Henno Brandsma
yesterday
It is clear how you found an $x$, but I still don't see what was wrong in my calculation.
– Rocco van Vreumingen
yesterday
@RoccovanVreumingen the $k$ is determined mod 1013 only.
– Henno Brandsma
yesterday
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 yesterday
Henno Brandsma
101k344107
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
yesterday
@RoccovanVreumingen I only computed the $x$ not the $k$.
– Henno Brandsma
yesterday
$x = r^{-1}(s-s')^{-1}(sH(m')-s'H(m))$ and this I could compute modulo $p-1$.
– Henno Brandsma
yesterday
It is clear how you found an $x$, but I still don't see what was wrong in my calculation.
– Rocco van Vreumingen
yesterday
@RoccovanVreumingen the $k$ is determined mod 1013 only.
– Henno Brandsma
yesterday
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 yesterday
Henno Brandsma
101k344107
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
yesterday
@RoccovanVreumingen I only computed the $x$ not the $k$.
– Henno Brandsma
yesterday
$x = r^{-1}(s-s')^{-1}(sH(m')-s'H(m))$ and this I could compute modulo $p-1$.
– Henno Brandsma
yesterday
It is clear how you found an $x$, but I still don't see what was wrong in my calculation.
– Rocco van Vreumingen
yesterday
@RoccovanVreumingen the $k$ is determined mod 1013 only.
– Henno Brandsma
yesterday
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 yesterday
Henno Brandsma
101k344107
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 yesterday
Henno Brandsma
101k344107
edited yesterday
answered yesterday
Henno Brandsma
101k344107
answered yesterday
Henno Brandsma
101k344107
answered yesterday
Henno Brandsma
101k344107
101k344107
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
yesterday
@RoccovanVreumingen I only computed the $x$ not the $k$.
– Henno Brandsma
yesterday
$x = r^{-1}(s-s')^{-1}(sH(m')-s'H(m))$ and this I could compute modulo $p-1$.
– Henno Brandsma
yesterday
It is clear how you found an $x$, but I still don't see what was wrong in my calculation.
– Rocco van Vreumingen
yesterday
@RoccovanVreumingen the $k$ is determined mod 1013 only.
– Henno Brandsma
yesterday
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
yesterday
@RoccovanVreumingen I only computed the $x$ not the $k$.
– Henno Brandsma
yesterday
$x = r^{-1}(s-s')^{-1}(sH(m')-s'H(m))$ and this I could compute modulo $p-1$.
– Henno Brandsma
yesterday
It is clear how you found an $x$, but I still don't see what was wrong in my calculation.
– Rocco van Vreumingen
yesterday
@RoccovanVreumingen the $k$ is determined mod 1013 only.
– Henno Brandsma
yesterday
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
yesterday
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
yesterday
@RoccovanVreumingen I only computed the $x$ not the $k$.
– Henno Brandsma
yesterday
@RoccovanVreumingen I only computed the $x$ not the $k$.
– Henno Brandsma
yesterday
$x = r^{-1}(s-s')^{-1}(sH(m')-s'H(m))$ and this I could compute modulo $p-1$.
– Henno Brandsma
yesterday
$x = r^{-1}(s-s')^{-1}(sH(m')-s'H(m))$ and this I could compute modulo $p-1$.
– Henno Brandsma
yesterday
It is clear how you found an $x$, but I still don't see what was wrong in my calculation.
– Rocco van Vreumingen
yesterday
It is clear how you found an $x$, but I still don't see what was wrong in my calculation.
– Rocco van Vreumingen
yesterday
@RoccovanVreumingen the $k$ is determined mod 1013 only.
– Henno Brandsma
yesterday
@RoccovanVreumingen the $k$ is determined mod 1013 only.
– Henno Brandsma
yesterday
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
yesterday
Why is that always meaningless?
– Rocco van Vreumingen
yesterday
Not quite always, but e.g. modulo $9$ all $x$ are multiples of $2$. E.g. $7 = 2cdot 8$ in that ring.
– Henno Brandsma
yesterday
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
yesterday
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
yesterday