Mfcttrf

Can I submit a paper computer science conference using an alias if using my real name can cause legal trouble in my original country

What's a good pattern to calculate a variable only when it is used the first time?

Output with the same length always

Unconventional examples of mathematical modelling

The Lucky House

Have there ever been other TV shows or Films that told a similiar story to the new 90210 show?

How to render "have ideas above his station" into German

Alignment of different align environment

Do predators tend to have vertical slit pupils versus horizontal for prey animals?

Representing an indicator function: binary variables and "indicator constraints"

What should I do with the stock I own if I anticipate there will be a recession?

Ending a line of dialogue with "?!": Allowed or obnoxious?

Would getting a natural 20 with a penalty still count as a critical hit?

μονάδαι as plural form of μονάς

Why is su world executable?

Eric Andre had a dream

Are there any rules on how characters go from 0th to 1st level in a class?

Radix2 Fast Fourier Transform implemented in C++

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

Replacing old plug-in 220V range with new hardwire 3-wire electric cooktop: remove outlet or add a plug?

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

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

global variant of csname…endcsname

Expressing a chain of boolean ORs using ILP

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 4 hours ago

yyyyyyy

9,90433 gold badges3535 silver badges5454 bronze badges

asked 9 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♦
  8 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 4 hours ago

yyyyyyy

9,90433 gold badges3535 silver badges5454 bronze badges

asked 9 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♦
  8 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 4 hours ago

yyyyyyy

9,90433 gold badges3535 silver badges5454 bronze badges

asked 9 hours ago

J. DoeJ. Doe

12399 bronze badges

$endgroup$

share|improve this question

edited 4 hours ago

yyyyyyy

9,90433 gold badges3535 silver badges5454 bronze badges

asked 9 hours ago

J. DoeJ. Doe

12399 bronze badges

share|improve this question

edited 4 hours ago

yyyyyyy

9,90433 gold badges3535 silver badges5454 bronze badges

asked 9 hours ago

J. DoeJ. Doe

12399 bronze badges

edited 4 hours ago

yyyyyyy

9,90433 gold badges3535 silver badges5454 bronze badges

edited 4 hours ago

yyyyyyy

9,90433 gold badges3535 silver badges5454 bronze badges

asked 9 hours ago

J. DoeJ. Doe

12399 bronze badges

asked 9 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 6 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
  2 hours 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 6 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
  2 hours 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 6 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
  2 hours 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 6 hours ago

yyyyyyyyyyyyyy

9,90433 gold badges3535 silver badges5454 bronze badges

$endgroup$

share|improve this answer

answered 6 hours ago

yyyyyyyyyyyyyy

9,90433 gold badges3535 silver badges5454 bronze badges

answered 6 hours ago

yyyyyyyyyyyyyy

9,90433 gold badges3535 silver badges5454 bronze badges

answered 6 hours ago

yyyyyyyyyyyyyy

9,90433 gold badges3535 silver badges5454 bronze badges