Sharing secrets with polynomials

This post will present a couple ways to share secrets using polynomials. We have a group of n people who want to share a secret between them so that k of them will have to cooperate in order to unlock the secret. For example, maybe a committee of n = 5 wants to require the cooperation of at least k = 3 members.

Shamir’s method

Adi Shamir came up with the idea of using polynomials to share secrets as follows. First, encode the secret you want to share as an integer a0. Next, generate m = k-1 other random integers a1 through am and use these as coefficients of a polynomial f of degree m:

f(x) = a_0 + a_1x + a_2x^2 + \cdots + a_mx^m

A trusted party generates n random integers values of x and gives each person an x and the corresponding value of f(x). Since m+1 points completely determine a mth degree polynomial, if k = m+1 people share their data, they can recover f, and thus recover the secret number a0. This can be efficiently, for example, by using Lagrange interpolation. But with fewer than k data points, the polynomial remains undetermined.

In practice we’d work over the integer modulo a large prime p. While fewer than k data points will not let someone completely determine the polynomial f, it will narrow down the possible coefficients if we’re working over the integers. Working modulo a large prime instead reveals less information.

Verifiable secret sharing

There’s a possible problem with Shamir’s method. Maybe the trusted party made a mistake. Or maybe the trusted party was dishonest and shouldn’t have been trusted. How can the parties verify that they have been given valid data without unlocking the secret? Seems we’re at a logical impasse since you’d have to recover the polynomial to know if your points are on the polynomial.

Paul Feldman came up with a way to assure the participants that the secret can be unlocked without giving them the information to unlock it. The trick is to give everyone data that in principle would let them determine the polynomial, but in practice would not.

We choose a large prime p such that p-1 has a large prime factor q [1]. Then the multiplicative group of non-zero integers mod p has a subgroup of order q. Let g be a generator of that group. The idea is to let everyone verify that

y_i = f(x_i)

for their given (xi, yi) by letting them verify that

g^{y_i} = g^{f(x_i)}

where all calculations are carried out mod p. Our trusted party does this by computing

A_i \equiv g^{a_i}\pmod{p}

for each coefficient ai and letting everyone know g and each of the Ai‘s.

In principle, anyone could solve for a0 if they know A0. But in practice, provided q is large enough, this would not be possible because doing so would require solving the discrete logarithm problem, which is computationally difficult. It’s possible to compute discrete logarithms for small q, but the difficulty goes up quickly as q gets larger.

How do the the Ai‘s let everyone verify that their (xi, yi) data is correct?

Each person can verify that

g^{y_i} = \prod_{j=0}^m A_j^{x_i^j} 

using the public data and their personal data, and so they can verify that

g^{y_i} = \prod_{j=0}^m A_j^{x_i^j} = \prod_{j=0}^m g^{a_j x_i^j} = g^{f(x_i)} 

Related posts

[1] Conceptually you pick p‘s until you find one so that p-1 has a large prime factor q. In practice, you’d do it the other way around: search for large primes q until you find one such that, say, 2q + 1 is also prime.

Addition on Curve1174

I’ve written about elliptic curve and alluded to the fact that there’s a special kind of addition for points on the curve. But I haven’t gone into details because it’s more complicated than I wanted to get into.

However, there’s a special case where the details are not complicated, the so called Edwards curves. I’ll look briefly at Edwards curves in general, then focus on Curve1174, a particular Edwards curve used in cryptography.

The example here could be used in an introductory group theory course with no reference to elliptic curves. Just think of it as a funny way to add pairs of integers. Continue reading

Groups of order 2019

How many groups have 2019 elements? What are these groups?

2019 is a semiprime, i.e. the product of two primes, 3 and 673. For every semiprime s, there are either one or two distinct groups of order s.

As explained here, if spq with pq, all groups of order s are isomorphic if q is not a factor of p-1. If q does divide p-1 then there are exactly two non-isomorphic groups of order s, one abelian and one non-abelian. In our case, 3 does divide 672, so there are two groups of order 2019. The first is easy: the cyclic group of order 2019. The second is more complex.

You could take the direct product of the cyclic groups of order 3 and 673, but that turns out to be isomorphic to the cyclic group of order 2019. But if you take the semidirect product you get the other group of order 2019, the non-abelian one.

Semidirect products

Starting with two groups G and H, the direct product G × H is the Cartesian product of G and H with multiplication defined componentwise. The semidirect product of G and H, written [1]

G \rtimes H

also starts with the Cartesian product of G and H but defines multiplication differently.

In our application, G will be the integers mod 673 with addition and H will be a three-element subgroup of the integers mod 673 with multiplication [2]. Let H be the set {1, 255, 417} with respect to multiplication [3]. Note that 1 is its own inverse and 255 and 417 are inverses of each other.

Product

Now the group product of (g1, h1) and (g2, h2) is defined to be

(g1 + h1-1g2, h1 h2)

So, for example, the product of (5, 255) and (334, 417) is (5 + 417*334, 255*417) which reduces to (645, 1) working mod 673.

(We haven’t defined the semidirect product in general, but the procedure above suffices to define the semidirect product for any two groups of prime order, and so it is sufficient to find all groups of semiprime order.)

Note that our group is non-abelian. For example, if we reverse the order of multiplication above we get (263, 1).

Identity

The identity element is just the pair consisting of the identity elements from G and H. In our case, this is (0, 1) because 0 is the additive identity and 1 is the multiplicative identity.

Inverse

The inverse of an element (gh) is given by

(-ghh-1).

So, for example, the inverse of (600, 255) is (444, 417).

Python code

The goal of this post is to be concrete rather than general.

So to make everything perfectly explicit, we’ll write a little Python code implementing the product and inverse.

    
    def hinv(h):
        if h == 255:
            return 417
        if h == 417:
            return 255
        if h == 1:
            return 1
    
    def prod(x, y):
        g1, h1 = x
        g2, h2 = y
        g3 = (g1 + hinv(h1)*g2) % 673
        h3 = (h1*h2) % 673
        return (g3, h3)
    
    def group_inv(x):
        g, h = x
        return ((-g*h)%673, hinv(h))
    
    x = (5, 255)
    y = (334, 417)
    print(prod(x, y))
    print(prod(y, x))
    print(group_inv((600, 255)))

The following code verifies that our group satisfies the axioms of a group.

    from itertools import product
    
    identity = (0, 1)
    h_list = [1, 255, 417]
    
    def elem(x):
        g, h = x
        g_ok = (0 <= g <= 672)
        h_ok = (h in h_list)
        return (g_ok and h_ok)
    
    group = product(range(673), h_list)
    assert(len([g for g in group]) == 2019)
    
    # closed under multiplicaton    
    for x in group:
        for y in group:
            assert( elem(prod(x, y)) )
    
    # multiplication is associative
    for x in group:
        for y in group:
            for z in group:
                xy_z = prod(prod(x, y),z)
                x_yz = prod(x, prod(y,z))
                assert(xy_z == x_yz)
    
    # identity acts like it's supposed to
    for x in group:
        assert( prod(x, identity) == x )
        assert( prod(identity, x) == x )
    
    # every element has an inverse
    for x in group:
        ginv = group_inv(x)
        assert( elem(ginv) )
        assert( prod(x, ginv) == identity )
        assert( prod(ginv, x) == identity )

Related posts

[1] The symbol for semidirect product is ⋊. It’s U+22CA in Unicode and \rtimes in LaTeX.

[2] In general, the semidirect product depends on a choice of an action of the group H on the group G. Here the action is multiplication by an element of H. Different actions can result in different groups. Sometimes the particular choice of action is made explicit as a subscript on the ⋊ symbol.

[3] How did I find these numbers? There are 672 non-zero numbers mod 673, so I picked a number, it happened to be 5, and raised it to the powers 672/3 and 2*672/3.

 

Groups of semiprime order

For each prime p, there is only one group with p elements, the cyclic group with that many elements. It would be plausible to think there is only one group of order n if and only if n is prime, but this isn’t the case.

If p and q are primes, then there are ostensibly at least two groups of order pq: the cyclic group Zpq, and Zp + Zq, the direct sum of the cyclic groups of orders p and q. However, there may just be one group of order pq after all because the two groups above could be isomorphic.

If pq = 2, then Z4 and Z2 + Z2 are not isomorphic. But the groups Z15 and Z3 + Z5 are isomorphic. That is, there is only one group of order 15, even though 15 is composite. This is the smallest such example.

Let p and q be primes with pq. If q does not divide p-1, then there is only one group of order pq. That is, all groups of order pq are isomorphic to the cyclic group Zpq. So when p = 5 and q = 3, there is only one group of order 15 because 3 does not evenly divide 5-1 = 4. The same reasoning shows, for example, that there must only be one group with 77 elements because 7 does not divide 10.

Now if q does divide p-1, then there are two distinct groups of order pq. One is the cyclic group with pq elements. But the other is non-Abelian, and so it cannot be Zp + Zq. So once again Zpq is isomorphic to Zp + Zq, but there’s a new possibility, a non-Abelian group.

Note that this does not contradict our earlier statement that Z4 and Z2 + Z2 are different groups, because we assumed p > q. If pq, then Zpq is not isomorphic to Zp + Zq.

Related posts

 

Number of groups of prime power order

John Baez left a comment on my post on group statistics saying

It’s known that the number of groups of order p^n for prime p is p^{2n^3/27+O(n^(8/3))}. It might be fun to compare this to what Mathematica says.

Here goes. First let’s let p = 2. Mathematica’s FiniteGroupCount function tops out at n = 10. And for the range of values Mathematica does support, 2^{2n^3/27} grossly overestimates the number of groups.

    Table[{FiniteGroupCount[2^n], 2^((2./27) n^3)}, {n, 1, 11}]

    {{1, 1.05269}, {2, 1.50795}, {5, 4.}, {14, 26.7365}, 
    {51, 612.794}, {267, 65536.}, {2328, 4.45033*10^7}, 
    {56092, 2.61121*10^11}, {10494213, 1.80144*10^16}, 
    {49487365422, 1.98847*10^22}, {FiniteGroupCount[2048], 4.7789*10^29}}

OEIS has entries for the sizes of various groups, and the entry for powers of 2 confirms the asymptotic formula above. Maybe it’s not a good approximation until n is very large. (Update: Here’s a reference for the asymptotic expression for all p.)

The OEIS entry for number of groups of order powers of 5 has an interesting result:

For a prime p >= 5, the number of groups of order p^n begins 1, 1, 2, 5, 15,
61 + 2*p + 2*gcd (p – 1, 3) + gcd (p – 1, 4),
3*p^2 + 39*p + 344 + 24*gcd(p – 1, 3) + 11*gcd(p – 1, 4) + 2*gcd(p – 1, 5), …

We can duplicate this with Mathematica.

    Table[FiniteGroupCount[5^n], {n, 0, 6}]

    {1, 1, 2, 5, 15, 77, 684}

and the last two numbers match the calculations given in OEIS.

There’s something interesting going on with Mathematica. It doesn’t seem to know, or agree with, the formula above for groups of order p4. For example,

    Table[FiniteGroupCount[7^n], {n, 0, 6}]

    {1, 1, 2, 5, FiniteGroupCount[2401], 83, 860}

I get similar results when I use larger primes: it can’t handle the fourth power.

    Table[FiniteGroupCount[389^n], {n, 0, 6}]

    {1, 1, 2, 5, FiniteGroupCount[22898045041], 845, 469548}

The results for n = 5 and 6 agree with OEIS.

Is OEIS wrong about the number of groups of order p4 or should Mathematica simply return 15 but there’s a gap in the software?

Also, does anybody know why the agreement with the asymptotic formula above is so bad? It’s just as bad or worse for other primes that I tried.

Related posts

Group statistics

I just ran across FiniteGroupData and related functions in Mathematica. That would have made some of my earlier posts easier to write had I used this instead of writing my own code.

Here’s something I find interesting. For each n, look at the groups of order at most n and count how many are Abelian versus non-Abelian. At first there are more Abelian groups, but the non-Abelian groups soon become more numerous. Also, the number of Abelian groups grows smoothly, while the number of non-Abelian groups has big jumps, particularly at powers of 2.

Counting Abelian and non-Abelian groups

Here’s the Mathematica code:

    fgc = FoldList[Plus, 0, Table[FiniteGroupCount[n], {n, 1, 300}]]
    fga = FoldList[Plus, 0, Table[FiniteAbelianGroupCount[n], {n, 1, 300}]]
    ListLogPlot[ {fgc - fga, fga }, 
        PlotLegends -> {"Non-Abelian", "Abelian"}, 
        Joined -> True, 
        AxesLabel -> {"order", "count"}]

I see the plot legend on my screen, but when saving the plot to a file the legend wasn’t included. Don’t know why. (Update: See footnote [1]). The jagged blue curve is the number of non-Abelian groups of size up to n. The smooth gold curve is the corresponding curve for Abelian groups.

Here’s the same plot carried out further to show the jumps at 512 and 1024.

Counting Abelian and non-Abelian groups

Related posts

[1] Someone from Wolfram Research saw this post and sent me a fix:

pl = ListLogPlot[...]
Export["~/Desktop/img.png", pl]

Overlap in the classification of finite simple groups

The previous post defined the groups PSL(nq) where n is a positive integer and q is a prime power. These are finite simple groups for n ≥ 2 except for PSL(2, 2) and PSL(2, 3).

Overlap among PSL(nq)

There are a couple instances where different values of n and q lead to isomorphic groups: PSL(2, 4) and PSL(2, 5) are isomorphic, and PSL(2, 7) and PSL(3, 2) are isomorphic. These are the only instances [1].

With the exceptions stated above, distinct values of n and q lead to distinct groups. Is it possible for different choices of n and q to lead to groups of the same size, even though the groups are not isomorphic to each other? Yes, PSL(3, 4) and PSL(4, 2) both have order 20160, but the groups are not isomorphic. This is the only example [2].

Overlap between PSL and alternating groups

The first post in this series mentioned that for n ≥ 5, the alternating group An, the group of even permutations on a set of n elements, is a simple group. Three of the alternating groups are isomorphic to PSL groups:

  • PSL(2, 4) = PSL(2, 5) = A5
  • PSL(2, 9) = A6
  • PSL(4, 2) = A8

Here “=” really means isomorphic. We mentioned PSL(4, 2) above. It has the same order as PSL(3, 4). This means that A8 and PSL(3, 4) have the same order but are not isomorphic.

I suspect that with a small number of exceptions, the order of a finite simple group determines the group. I haven’t proven that, but numerical exploration suggests its true. This page lists non-Abelian finite simple groups of order less than 10 billion, and there are only seven orders that correspond to more than 1 group, the largest example being order 25,920.

One last overlap

There is only one other duplication in the lists of groups in the CFSG theorem, and that is PSU(4, 2) = PSp(4, 3). I haven’t written about these groups yet.

Notes

[1] See The Finite Simple Groups by Robert A. Wilson

[2] In fact, aside from the groups mentioned in this post, the orders of all the finite simple groups are unique except for two non-isomorphic families that have orders: PΩ2n+1(q) and PSp2n(q) for n ≥ 3 and odd prime powers q. See discussion on Math Overflow.

Orders of finite simple groups

Simple groups are to groups as prime numbers are to numbers.A simple group has no non-trivial normal subgroups, just as a prime number has no non-trivial factors.

Classification

Finite simple groups have been classified into five broad categories:

  1. Cyclic groups of prime order
  2. Alternating groups
  3. Classical groups
  4. Exceptional groups of Lie type
  5. Sporadic groups.

Three of these categories are easy to describe.

The cyclic groups of prime order are simply the integers mod p where p is prime. These are the only Abelian finite simple groups.

The alternating groups are even-order permutations of a set. These groups are simple if the set it permutes has at least 5 elements.

The sporadic groups are a list of 26 groups that don’t fit anywhere else. The other categories are infinite families of groups, but the sporadic groups are just individual groups.

The classical groups and exceptional Lie groups are harder to describe. I’d like to write about them in some detail down the road. For now, I’ll be deliberately vague.

This post is a broad overview, and may be the first of more posts in a series. This post just looks at the sizes (orders) of the groups.

Update: Here’s a follow-on post that looks at the groups denoted An(q).

Smallest group in each family

You can find a list of the families of finite simple groups on Wikipedia, along with their orders (the number of elements in each group). We can use this to determine the smallest group in each family, just to get an idea of how these families spread out.

The classical groups and exceptional Lie groups that I glossed over depend on a parameter n and/or a parameter q where q is a prime power. Even for very small values of n and q, the smallest ones for which the groups are simple, some of these groups are BIG.

|------------------+----------------------------------------------|
| Family           |               Order of smallest simple group |
|------------------+----------------------------------------------|
| Cyclic(p)        |                                            2 |
| Alternating(n)   |                                           60 |
| A_n(q)           |                                           60 |
| Sporadic         |                                         7920 |
| B_n(q)           |                                        25920 |
| Suzuki(2^(2n+1)) |                                        29120 |
| 2A_n(q^2)        |                                       126000 |
| C_n(q)           |                                      1251520 |
| G_2(q)           |                                      4245696 |
| 2F_4(q)'         |                                     17971200 |
| D_n(q)           |                                    174182400 |
| 3D_n(q^2)        |                                    197406720 |
| 3D_4(q^3)        |                                    211341312 |
| 2G_2(q)          |                                  10073444472 |
| F_4(q)           |                             3311126603366400 |
| 2E_6(q^2)        |                      76532479683774853939200 |
| E_6(q)           |                     214841575522005575270400 |
| 2F_4(q)          |                     264905352699586176614400 |
| E_7(q)           |     7997476042075799759100487262680802918400 |
| E_8(q)           | 33780475314363480626138819061408559507999169 |
|------------------+----------------------------------------------|

Never mind the cryptic family names for now; I may get into these in future posts. My point here is that for some of these families, even the smallest member is quite large.

Interestingly, the smallest sporadic group has a modest size of 7920. But the largest sporadic group, “The Monster,” has order nearly 1054. You could think of each sporadic group of being a lonely family of one, so I’ll list their orders here. (There are groupings within the sporadic groups, but I’m not clear how much these are grouped together for historical reasons (i.e. who discovered them) or mathematical reasons. I expect there’s a blurry line between the historical and mathematical since the groups discovered by an individual were amenable to that person’s techniques.)

|-------+--------------------------------------------------------|
| Group |                         Order of smallest simple group |
|-------+--------------------------------------------------------|
| M_11  |                                                   7920 |
| M_12  |                                                  95040 |
| J_1   |                                                 175560 |
| M_22  |                                                 443520 |
| J_2   |                                                 604800 |
| M_23  |                                               10200960 |
| HS    |                                               44352000 |
| J_3   |                                               50232960 |
| M_24  |                                              244823040 |
| McL   |                                              898128000 |
| He    |                                             4030387200 |
| Ru    |                                           145926144000 |
| Suz   |                                           448345497600 |
| O'N   |                                           460815505920 |
| Co_3  |                                           495766656000 |
| Co_2  |                                         42305421312000 |
| Fi_22 |                                         64561751654400 |
| HN    |                                        273030912000000 |
| Ly    |                                      51765179004000000 |
| Th    |                                      90745943887872000 |
| Fi_23 |                                    4089470473293004800 |
| Co_1  |                                    4157776806543360000 |
| J_4   |                                   86775571046077562880 |
| Fi_24 |                              1255205709190661721292800 |
| B     |                     4154781481226426191177580544000000 |
| M     | 808017424794512875886459904961710757005754368000000000 |
|-------+--------------------------------------------------------|

Groups of order less than a million

In 1972, Marshall Hall published a list of the (non-Abelian) finite simple groups of order less than one million. Hall said that there were 56 such groups known, and now that the classification theorem has been completed we know he wasn’t missing any groups.

There are 78,498 primes less than one million, so there are that many cyclic (Abelian) finite groups of order less than one million. In the range of orders one to a million, Abelian simple groups outnumber non-Abelian simple groups by over 1400 to 1. Of the 56 non-Abelian orders, 46 belong to groups of the form An(q). Most of the families in the table above don’t make an appearance since their smallest representatives have order much larger than one million.

There can be multiple non-isomorphic groups with the same order, especially for small orders. This is another detail I may get into in future posts.

Growth of group orders

Now let’s look at plots to see how the size of the groups grow. Because these numbers quickly get very large, all plots are on a log scale.

In case you have difficulty seeing the color differences, the legends are in the same vertical order as the plots.

Some of the captions list two or three groups. That is because the curves corresponding to the separate groups are the same at the resolution of the image.

Here are groups that only depend on a parameter n.

Here are groups that only depend on a parameter q. The q‘s vary over prime powers: 2, 3, 4, 5, 7, 8, 9, 11, etc. Note that the horizontal axis is not q itself but the index of q, i.e. i on the horizontal scale corresponds to the ith prime power.

For the groups that depend on n and q, we vary these separately. First we hold n fixed at 5 and let q vary.

Finally, we now fix q at 5 and let n vary.

Looking up group by size

Imagine writing a program that takes the size n of a finite simple group and tells you what groups it could be. What would such a program look like?

Since the vast majority of finite simple groups below a given size are cyclic, we’d check whether n is prime. If it is, then the group is the integers mod n. What about the non-Abelian groups? These are so thinly spread out that the simplest thing to do would be to make a table of the possible values less than the maximum program input size N. If we set N = 10,000,000,000, then David Madore has already been done here. There are only 491 possible orders for non-Abelian simple groups of order less than 10 billion.

We said above that Abelian groups outnumbered non-Abelian groups by over 1400 to 1 for simple groups of order less than one million. What about for simple groups of order less than 10 billion? The number of primes less than 10 billion is 455,052,511 and so Abelian simple groups outnumber non-Abelian simple groups by a little less than a million to one.

Conclusion

This post began by saying simple groups are analogous to prime numbers. The Abelian finite simple groups are exactly integers modulo prime numbers. The orders of the non-Abelian finite simple groups are spread out much more sparsely than prime numbers.

Also, the way you combine simple groups to make general groups is more complicated than the way you multiply prime numbers to get all integers. There was speculation that group theory would die once finite simple groups were classified, but that has not been the case. Unfortunately (or fortunately if you’re a professional group theorist) the classification theorem doesn’t come close to telling us everything we’d want to know about groups.

A tale of two elliptic curves

A few days ago I blogged about the elliptic curve secp256k1 and its use in Bitcoin. This curve has a sibling, secp256r1. Note the “r” in the penultimate position rather than a “k”. Both are defined in SEC 2: Recommended Elliptic Curve Domain Parameters. Both are elliptic curves over a field zp where p is a 256-bit prime (though different primes for each curve).

The “k” in sepc256k1 stands for Koblitz and the “r” in sepc256r1 stands for random. A Koblitz elliptic curve has some special properties that make it possible to implement the group operation more efficiently. It is believed that there is a small security trade-off, that more “randomly” selected parameters are more secure. However, some people suspect that the random coefficients may have been selected to provide a back door.

Both elliptic curves are of the form y² = x³ + ax + b. In the Koblitz curve, we have

a = 0
b = 7

and in the random case we have

a = FFFFFFFF 00000001 00000000 00000000 00000000 FFFFFFFF FFFFFFFF FFFFFFFC
b = 5AC635D8 AA3A93E7 B3EBBD55 769886BC 651D06B0 CC53B0F6 3BCE3C3E 27D2604B

You can find the rest of the elliptic curve parameters in the SEC 2 report. For some help understanding what the parameters mean and how to decode them, see my earlier post.

The NSA recommends the random curve for government use. It is also known as NIST P-256. Or rather it did recommend P-256 as part of its Suite B of cryptography recommendations. In August 21015 the NSA announced its concern that in the future, quantum computing could render the Suite B methods insecure. As far as we know, quantum computing at scale is years, maybe decades, away. But it takes a long time to develop quality encryption methods, and so the NSA and NIST are urging people to think ahead. (Update: The NSA recommends P-384 until post quantum methods mature.)

Bitcoin chose to use the less popular Koblitz curve for the reasons mentioned above, namely efficiency and concerns over a possible back door in the random curve. Before Bitcoin, secp256k1 was not widely used.

Related post: RSA numbers and factoring

Schnorr groups

Claus Schnorr

Schnorr groups, named after Claus Schnorr, are multiplicative subgroups of a finite field. They are designed for cryptographic application, namely as a setting for hard discrete logarithm problems.

The application of Schnorr groups to Schnorr signatures was patented, but the patent ran out in 2008.

There has been a proposal to include Schnorr signatures in Bitcoin, but it has not been accepted at this point. (The proposal would use Schnorr signatures but over an elliptic curve rather than a Schnorr group.)

Group construction

Pick a large prime p. Then the integers mod p form a finite field. The non-zero elements form an Abelian group of order p-1 under multiplication. Then p – 1 is composite, and so it can be factored into qr where q is prime. We want q to be large as well because it will be the order of our Schnorr group.

Pick any h such that hr is not congruent to 1 mod p. Then g = hr is the generator of our Schnorr group. Why does g have order q? A simple calculation shows

g^q \equiv h^{qr} \equiv h^{p-1} \equiv 1 \pmod p

where the last step follows from Fermat’s little theorem. This shows that the order of g is either q or a divisor of q, but by construction g is not congruent to 1 (mod p), and q has no other factors since it is prime.

Python code

Here’s a toy example using small numbers. Let p = 23, q = 11 and r = 2. Then we can pick h to be any number that is not a root of 1 (mod 23), i.e. any number except 1 or 22. Say we pick h = 7. Then g = 49 = 3 (mod 23).

Here’s a Python script to verify our claims and print out the elements of our Schnorr group.

    from sympy import isprime
    
    p, q, r, h = 23, 11, 2, 7
    
    assert(isprime(p))
    assert(isprime(q))
    assert(p-1 == q*r)
    
    g = h**r % p
    assert(g != 1)
    assert(g**q % p == 1)
    
    for i in range(q):
        print( g**i % p )

This shows that our group elements are {1, 3, 9, 4, 12, 13, 16, 2, 6, 18, 8}.

In theory we could use the same script with much larger numbers, but in that case we wouldn’t want to print out the elements. Also, the code would take forever. We naively computed ab (mod m) by computing ab first, then taking the remainder modulo m. It is far more efficient to reduce modulo m along the way. That’s what Python’s three-argument pow function does.

Here’s a revised version that runs quickly with large numbers.

    from sympy import isprime
    
    p = 115792089237316195423570985008687907852837564279074904382605163141518161494337
    q = 341948486974166000522343609283189
    r = 338624364920977752681389262317185522840540224
    h = 3141592653589793238462643383279502884197
    
    assert(isprime(p))
    assert(isprime(q))
    assert(p-1 == q*r)
    
    g = pow(h, r, p)
    assert(g != 1)
    assert(pow(g, q, p) == 1)

Related posts

Photo of Claus Schnorr by Konrad Jacobs CC BY-SA 2.0 de