Xjyuk

Pocket Clarketech

Why do aircraft leave cruising altitude long before landing just to circle?

What are some tips and tricks for finding the cheapest flight when luggage and other fees are not revealed until far into the booking process?

Output the list of musical notes

What exactly happened to the 18 crew members who were reported as "missing" in "Q Who"?

Unconventional examples of mathematical modelling

Output with the same length always

What are the advantages of this gold finger shape?

Subgroup generated by a subgroup and a conjugate of it

Why is the battery jumpered to a resistor in this schematic?

My new Acer Aspire 7 doesn't have a Legacy Boot option, what can I do to get it?

Why was ramjet fuel used as hydraulic fluid during Saturn V checkout?

Reducing contention in thread-safe LruCache

Number of matrices with bounded products of rows and columns

What allows us to use imaginary numbers?

C++ Least cost swapping 2

Why can't I see 1861 / 1871 census entries on Freecen website when I can see them on Ancestry website?

A reccomended structured approach to self studying music theory for songwriting

What should I do if actually I found a serious flaw in someone's PhD thesis and an article derived from that PhD thesis?

Photoshop older default brushes

Polar contour plot in Mathematica?

Why should P.I be willing to write strong LOR even if that means losing a undergraduate from his/her lab?

May the tower use the runway while an emergency aircraft is inbound?

What is the purpose/function of this power inductor in parallel?

Does knowing that the exponent is in a certain range help solving discrete log?

Why is “multiplying” $g^x$ and $g^y$ not possible?Discrete logarithm key sizes for very short term usageOn discrete logarithm problemSolving the discrete logarithm problem for a weak groupTrouble understanding the correctness of this Zero-Knowledge proof of posession of a discrete logDoes a different exponent and base but same key help to resolve discrete logarithm?How safe is a prime with $P=2 cdot Q cdot R cdot S cdot t+1$ for discrete logarithm? How to enhance/compare?How to determine if $n cdot g^a mod P$ and $m cdot g^a mod P$ generate the same sets? (set size < $P-1$)

.everyoneloves__top-leaderboard:empty,.everyoneloves__mid-leaderboard:empty,.everyoneloves__bot-mid-leaderboard:empty margin-bottom:0;

2

$begingroup$

given:
$c=g^i bmod P$
$g$ generator for group with group size $varphi(P)$
$g,P,varphi(P)$,c is known by the attacker

He wants to know $i$.

Now the attacker also knows $j,k$ with $j<i<k$
$k-j$ is too big to compute them all but it is much smaller than group size.

Does this knowledge about $i$ help the attacker?

diffie-hellman discrete-logarithm attack

share|improve this question

edited 3 hours ago

yyyyyyy

9,90433 gold badges3535 silver badges5454 bronze badges

asked 8 hours ago

J. DoeJ. Doe

12399 bronze badges

$endgroup$

• 
  
  
  

  
  2
  

  
  
  
  
  
  

  
  $begingroup$
  I think this allows an attack in time $sqrtk-j$ but I don't know for sure...
  $endgroup$
  – SEJPM♦
  7 hours ago
  

  
  
  
  

add a comment | 

2

$begingroup$

given:
$c=g^i bmod P$
$g$ generator for group with group size $varphi(P)$
$g,P,varphi(P)$,c is known by the attacker

He wants to know $i$.

Now the attacker also knows $j,k$ with $j<i<k$
$k-j$ is too big to compute them all but it is much smaller than group size.

Does this knowledge about $i$ help the attacker?

diffie-hellman discrete-logarithm attack

share|improve this question

edited 3 hours ago

yyyyyyy

9,90433 gold badges3535 silver badges5454 bronze badges

asked 8 hours ago

J. DoeJ. Doe

12399 bronze badges

$endgroup$

• 
  
  
  

  
  2
  

  
  
  
  
  
  

  
  $begingroup$
  I think this allows an attack in time $sqrtk-j$ but I don't know for sure...
  $endgroup$
  – SEJPM♦
  7 hours ago
  

  
  
  
  

add a comment | 

$begingroup$

given:
$c=g^i bmod P$
$g$ generator for group with group size $varphi(P)$
$g,P,varphi(P)$,c is known by the attacker

He wants to know $i$.

Now the attacker also knows $j,k$ with $j<i<k$
$k-j$ is too big to compute them all but it is much smaller than group size.

Does this knowledge about $i$ help the attacker?

diffie-hellman discrete-logarithm attack

share|improve this question

edited 3 hours ago

yyyyyyy

9,90433 gold badges3535 silver badges5454 bronze badges

asked 8 hours ago

J. DoeJ. Doe

12399 bronze badges

$endgroup$

share|improve this question

edited 3 hours ago

yyyyyyy

9,90433 gold badges3535 silver badges5454 bronze badges

asked 8 hours ago

J. DoeJ. Doe

12399 bronze badges

share|improve this question

edited 3 hours ago

yyyyyyy

9,90433 gold badges3535 silver badges5454 bronze badges

asked 8 hours ago

J. DoeJ. Doe

12399 bronze badges

edited 3 hours ago

yyyyyyy

9,90433 gold badges3535 silver badges5454 bronze badges

edited 3 hours ago

yyyyyyy

9,90433 gold badges3535 silver badges5454 bronze badges

asked 8 hours ago

J. DoeJ. Doe

12399 bronze badges

asked 8 hours ago

J. DoeJ. Doe

12399 bronze badges

1 Answer
1

active

oldest

votes

4

$begingroup$

The basic baby-step-giant-step algorithm can be tweaked to make use of this information.
The following algorithm takes $Theta(!sqrtk-j)$ group operations.

1. Let $h:=ccdot g^-j-1$, which equals $g^i-j-1$.


2. Pick some integer $mgeqsqrtk-j-1$.


3. Initialize an empty lookup table $T$.


4. For all $0leq a<m$, compute $g^ma$ and store $T[g^ma]:=a$.


5. For all $0leq b<m$, compute $g^-bh$ and check if $g^-bh$ is in $T$. When a match is found, return $j+1+mcdot T[g^-bh]+b$.

Note that this is almost exactly the standard BSGS algorithm, except for replacing the unknown exponent $i$ by $i-j-1$ in step 1 and adjusting the output accordingly in step 5.

---

Correctness:
If the algorithm returns something, it must be of the form $r=j+1+malpha+beta$ with $0leqalpha,beta<m$ and $T[g^-betah]=T[g^malpha]$.
This implies
$$
g^r
= g^j+1+malpha+beta
= g^j+1-beta+(i-j-1)+beta
= g^i
text,
$$
hence $r=i$ (modulo the order of $g$).

Completeness: Let $b:=(i-j-1)bmod m$ and $a:=(i-j-1-b)/m$.
These values are in the range $0leq a,b<m$ and satisfy $-b+i-j-1=ma$, hence will be found by the algorithm.

share|improve this answer

answered 5 hours ago

yyyyyyyyyyyyyy

9,90433 gold badges3535 silver badges5454 bronze badges

$endgroup$

• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  thanks for answer. I checked b-s-g-s before and thought it won't work for big numbers because you need a lot of storage in 4. However bigger number almost always work. With the knowledge about the index it will be much faster.
  $endgroup$
  – J. Doe
  1 hour ago
  

  
  
  
  

add a comment | 

Your Answer

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
);



);

draft saved

draft discarded

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

Name

Email

Required, but never shown

StackExchange.ready(
function ()
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fcrypto.stackexchange.com%2fquestions%2f72648%2fdoes-knowing-that-the-exponent-is-in-a-certain-range-help-solving-discrete-log%23new-answer', 'question_page');

);

Post as a guest

Name

Email

Required, but never shown

4

$begingroup$

The basic baby-step-giant-step algorithm can be tweaked to make use of this information.
The following algorithm takes $Theta(!sqrtk-j)$ group operations.

1. Let $h:=ccdot g^-j-1$, which equals $g^i-j-1$.


2. Pick some integer $mgeqsqrtk-j-1$.


3. Initialize an empty lookup table $T$.


4. For all $0leq a<m$, compute $g^ma$ and store $T[g^ma]:=a$.


5. For all $0leq b<m$, compute $g^-bh$ and check if $g^-bh$ is in $T$. When a match is found, return $j+1+mcdot T[g^-bh]+b$.

Note that this is almost exactly the standard BSGS algorithm, except for replacing the unknown exponent $i$ by $i-j-1$ in step 1 and adjusting the output accordingly in step 5.

---

Correctness:
If the algorithm returns something, it must be of the form $r=j+1+malpha+beta$ with $0leqalpha,beta<m$ and $T[g^-betah]=T[g^malpha]$.
This implies
$$
g^r
= g^j+1+malpha+beta
= g^j+1-beta+(i-j-1)+beta
= g^i
text,
$$
hence $r=i$ (modulo the order of $g$).

Completeness: Let $b:=(i-j-1)bmod m$ and $a:=(i-j-1-b)/m$.
These values are in the range $0leq a,b<m$ and satisfy $-b+i-j-1=ma$, hence will be found by the algorithm.

share|improve this answer

answered 5 hours ago

yyyyyyyyyyyyyy

9,90433 gold badges3535 silver badges5454 bronze badges

$endgroup$

• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  thanks for answer. I checked b-s-g-s before and thought it won't work for big numbers because you need a lot of storage in 4. However bigger number almost always work. With the knowledge about the index it will be much faster.
  $endgroup$
  – J. Doe
  1 hour ago
  

  
  
  
  

add a comment | 

4

$begingroup$

The basic baby-step-giant-step algorithm can be tweaked to make use of this information.
The following algorithm takes $Theta(!sqrtk-j)$ group operations.

1. Let $h:=ccdot g^-j-1$, which equals $g^i-j-1$.


2. Pick some integer $mgeqsqrtk-j-1$.


3. Initialize an empty lookup table $T$.


4. For all $0leq a<m$, compute $g^ma$ and store $T[g^ma]:=a$.


5. For all $0leq b<m$, compute $g^-bh$ and check if $g^-bh$ is in $T$. When a match is found, return $j+1+mcdot T[g^-bh]+b$.

Note that this is almost exactly the standard BSGS algorithm, except for replacing the unknown exponent $i$ by $i-j-1$ in step 1 and adjusting the output accordingly in step 5.

---

Correctness:
If the algorithm returns something, it must be of the form $r=j+1+malpha+beta$ with $0leqalpha,beta<m$ and $T[g^-betah]=T[g^malpha]$.
This implies
$$
g^r
= g^j+1+malpha+beta
= g^j+1-beta+(i-j-1)+beta
= g^i
text,
$$
hence $r=i$ (modulo the order of $g$).

Completeness: Let $b:=(i-j-1)bmod m$ and $a:=(i-j-1-b)/m$.
These values are in the range $0leq a,b<m$ and satisfy $-b+i-j-1=ma$, hence will be found by the algorithm.

share|improve this answer

answered 5 hours ago

yyyyyyyyyyyyyy

9,90433 gold badges3535 silver badges5454 bronze badges

$endgroup$

• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  thanks for answer. I checked b-s-g-s before and thought it won't work for big numbers because you need a lot of storage in 4. However bigger number almost always work. With the knowledge about the index it will be much faster.
  $endgroup$
  – J. Doe
  1 hour ago
  

  
  
  
  

add a comment | 

$begingroup$

The basic baby-step-giant-step algorithm can be tweaked to make use of this information.
The following algorithm takes $Theta(!sqrtk-j)$ group operations.

1. Let $h:=ccdot g^-j-1$, which equals $g^i-j-1$.


2. Pick some integer $mgeqsqrtk-j-1$.


3. Initialize an empty lookup table $T$.


4. For all $0leq a<m$, compute $g^ma$ and store $T[g^ma]:=a$.


5. For all $0leq b<m$, compute $g^-bh$ and check if $g^-bh$ is in $T$. When a match is found, return $j+1+mcdot T[g^-bh]+b$.

Note that this is almost exactly the standard BSGS algorithm, except for replacing the unknown exponent $i$ by $i-j-1$ in step 1 and adjusting the output accordingly in step 5.

---

Correctness:
If the algorithm returns something, it must be of the form $r=j+1+malpha+beta$ with $0leqalpha,beta<m$ and $T[g^-betah]=T[g^malpha]$.
This implies
$$
g^r
= g^j+1+malpha+beta
= g^j+1-beta+(i-j-1)+beta
= g^i
text,
$$
hence $r=i$ (modulo the order of $g$).

Completeness: Let $b:=(i-j-1)bmod m$ and $a:=(i-j-1-b)/m$.
These values are in the range $0leq a,b<m$ and satisfy $-b+i-j-1=ma$, hence will be found by the algorithm.

share|improve this answer

answered 5 hours ago

yyyyyyyyyyyyyy

9,90433 gold badges3535 silver badges5454 bronze badges

$endgroup$

share|improve this answer

answered 5 hours ago

yyyyyyyyyyyyyy

9,90433 gold badges3535 silver badges5454 bronze badges

answered 5 hours ago

yyyyyyyyyyyyyy

9,90433 gold badges3535 silver badges5454 bronze badges

answered 5 hours ago

yyyyyyyyyyyyyy

9,90433 gold badges3535 silver badges5454 bronze badges