Group Theory Basics (Cyclic Groups, Discrete Log) TODO
Concept
A group is a set with a binary operation satisfying associativity, an identity element, and inverses; if the powers of a single element g generate the whole group, it's called cyclic, and g is called a generator. In a finite group, the order of an element is the size of the cyclic subgroup it generates, and by Lagrange's theorem, the size of any subgroup always divides the size of the whole group. The discrete logarithm problem asks: given g and h = g^x in a cyclic group, find the exponent x. Computing the exponent (exponentiation) is fast via repeated squaring, while going the other direction is believed to be hard in a well-chosen group — this asymmetry is the foundation of public-key cryptography. However, hardness depends entirely on the choice of group: if the order of a multiplicative group factors into only small primes, Pohlig-Hellman breaks the problem into smaller pieces, so the group's order needs to be a large prime. Elliptic curve groups are widely used in practice because they offer shorter element representations at the same security level.
When handling signatures or commitments, scalars need to be reduced modulo the group's order — without understanding this structure, it's easy to end up accepting out-of-range scalars or small-subgroup points without checking them, which creates a real vulnerability.
Code & Formula
# 군론 기초(순환군·이산로그) — Z_p^*의 생성원 찾기, 위수(Lagrange), 이산로그 브루트포스
# 교육용 예시: 실제 암호에는 훨씬 큰 소수를 쓴다.
p = 23 # 소수 => Z_p^* = {1,...,p-1}는 위수 p-1 = 22인 순환군
def order_of(g, p):
"""g의 위수: g^k = 1이 되는 최소 양의 k."""
k, x = 1, g % p
while x != 1:
x = (x * g) % p
k += 1
return k
group_order = p - 1
print(f"|Z_{p}^*| = {group_order}")
# 모든 원소의 위수를 나열하고 Lagrange 정리(위수는 항상 군의 크기를 나눔) 확인
orders = {g: order_of(g, p) for g in range(1, p)}
for g, o in orders.items():
assert group_order % o == 0, "Lagrange 정리 위반!"
print("각 원소의 위수(Lagrange 정리: 모두 22를 나눔):")
print({g: o for g, o in list(orders.items())[:6]}, "...")
# 위수가 group_order와 같은 원소 = 생성원(primitive root)
generators = [g for g, o in orders.items() if o == group_order]
print(f"\n생성원들: {generators}")
g = generators[0]
x_secret = 15 # 비밀 지수
h = pow(g, x_secret, p)
print(f"\ng={g}, h=g^x mod p={h} (x는 비밀)")
# 이산로그 브루트포스: h = g^x가 되는 x를 처음부터 찾아본다 (작은 군이라 가능)
for x in range(group_order):
if pow(g, x, p) == h:
print(f"브루트포스로 복원한 이산로그 x={x} (정답과 일치: {x == x_secret})")
break
print("-> 군이 커지면(p가 수백 비트) 이 브루트포스는 우주 나이보다 오래 걸린다 — 이 비대칭성이 공개키 암호의 토대.")
Exercise
For a small prime p, find a generator of the multiplicative group, list the order of every element, and confirm Lagrange's theorem; then brute-force the discrete log in the same group to get a feel for how the difficulty scales with size.
Practical Connection
The secp256k1 curve used by Ethereum signatures is a cyclic group of prime order, and failing to reduce the signature scalar modulo that order leads to real incidents such as signature malleability or key leakage through nonce issues.
Where it lands in Jayverse
- Wallet/Rabbit: reject signatures whose scalar isn't reduced mod the curve order or that use non-canonical (high-s) form. Add this check at the simulate-before-sign step for both regular ECDSA and any session-key/mandate signature.
- Auditor: add "signature malleability / small-subgroup check" as a standing methodology item. Apply it to every contract verifying ECDSA/EIP-712 signatures across Rabbit, Verex and Bridge, not just once at launch.
- Bridge: audit the lock-and-mint relayer's signature verification for the same group-order reduction. Bridge relayers using multisig or threshold signatures are a common target for exactly this bug class.
Key expressions
| Expression | 뜻 · 쓰이는 자리 |
|---|---|
| generate (the group) | (군을) 생성하다 · 한 원소의 거듭제곱들이 전체 군을 만들어낼 때. "generate the whole group" |
| believed to be hard | 어렵다고 여겨지는(증명되진 않은) · 아직 증명되지 않았지만 업계가 그렇다고 믿는 난이도를 말할 때. "is believed to be hard in a well-chosen group" |
| break ... into smaller pieces | ~을 더 작은 조각들로 쪼개다 · 어려운 문제를 쉬운 하위 문제들로 분해할 때. "Pohlig-Hellman breaks the problem into smaller pieces" |
| end up -ing | 결국 ~하게 되다 · 의도치 않게 취약한 상태로 귀결될 때. "it's easy to end up accepting out-of-range scalars" |
| reduced modulo | ~으로 나눈 나머지로 줄이다(모듈러 연산) · 값이 특정 군의 위수 범위 안으로 들어오게 맞출 때. "scalars need to be reduced modulo the group's order" |
| leakage through | ~을 통한 누출 · 특정 경로로 비밀 정보가 새어나갈 때. "key leakage through nonce issues" |
| Pohlig-Hellman | 폴리그-헬만 알고리즘 · 군의 위수가 작은 소수들로만 인수분해되면 이산로그 문제를 작은 조각들로 나눠 푸는 공격법, 그래서 위수는 큰 소수여야 함. "Pohlig-Hellman breaks the problem into smaller pieces" |
| Lagrange's theorem | 라그랑주 정리 · 유한군에서 부분군의 크기가 항상 전체 군의 크기를 나눈다는 정리, 원소의 위수를 추론하는 근거. "the size of any subgroup always divides the size" |
| signature malleability | 서명 가단성(같은 메시지에 대해 유효한 서명이 여러 개 존재하는 결함) · 스칼라를 위수로 리듀스하지 않을 때 발생하는 실제 취약점 사례. "real incidents such as signature malleability or key leakage" |
If you study this on a given day, add a note link and a ✅ to this line in the source curriculum (docs/knowledge/math-50-curriculum.md) and this spot will lead straight to the note body. You can also write directly on this page — but regenerating overwrites it, so it's safer to keep anything you want to save as markdown under docs/algorithms/.