Brute Force the Log

Public Values

The public group is tiny enough to search directly.

highlighted = computed this step

The public puzzle is tiny

The attacker sees prime p=23, base g=5, and public value y=8.

gx mod p=8g^x\bmod p=8
Public toy groupThe tiny discrete-log rows are recomputed from p, g, and the target public value.Public toy group - recovered=6quantityvaluek=15k=22k=310k=44k=520k=6 recovered8

The hidden question

The discrete-log question asks which exponent x makes g to x land on y.

find x\text{find }x
Public toy groupThe tiny discrete-log rows are recomputed from p, g, and the target public value.Public toy group - recovered=6quantityvaluek=15k=22k=310k=44k=520k=6 recovered8

Small groups can be searched

Because p is only 23, the table can try exponents directly.

p=23p=23
Public toy groupThe tiny discrete-log rows are recomputed from p, g, and the target public value.Public toy group - recovered=6quantityvaluek=15k=22k=310k=44k=520k=6 recovered8

Summary

A tiny group turns the hidden exponent into a short table search.

target=8\text{target}=8
Public toy groupThe tiny discrete-log rows are recomputed from p, g, and the target public value.Public toy group - recovered=6quantityvaluek=15k=22k=310k=44k=520k=6 recovered8