Week 3 Monday#

Screenshare notes#

Slide 1

Slide 2

Slide 3

Deepnote notebook#

Today’s class is mostly devoted to helping you better understand Lab 2, where you will perform a Diffie-Hellman Key Exchange with another group.

!pip install pycryptodome

Collecting pycryptodome
  Downloading pycryptodome-3.18.0-cp35-abi3-manylinux_2_17_x86_64.manylinux2014_x86_64.whl (2.1 MB)
     ━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━ 2.1/2.1 MB 86.1 MB/s eta 0:00:00
?25hInstalling collected packages: pycryptodome
Successfully installed pycryptodome-3.18.0
WARNING: You are using pip version 22.0.4; however, version 23.1.2 is available.
You should consider upgrading via the '/root/venv/bin/python -m pip install --upgrade pip' command.


from Crypto.Util.number import getPrime, getRandomNBitInteger
from sympy.ntheory import n_order, nextprime, isprime

p = getPrime(10)

p

683

The 10 in getPrime(10) refers to how many digits the prime is when written in binary.

pow(2, 10)

1024

pow(2, 9)

512

For example, a 30 digit prime (in ordinary base 10 digits) is between \(10^{29}\) and \(10^{30}\). Similarly, a 30-bit prime (meaning 30 digits in binary, in base 2) is between \(2^{29}\) and \(2^{30}\).

getPrime(30)

803359783

pow(2, 29)

536870912

pow(2, 30)

1073741824

p

683

Let’s find a generator modulo p = 683.

n_order(1, p)

1

n_order(2, p)

22

# Want p-1
p-1

682

n_order(0, p)

---------------------------------------------------------------------------
ValueError                                Traceback (most recent call last)
Cell In [16], line 1
----> 1 n_order(0, p)

File /shared-libs/python3.9/py/lib/python3.9/site-packages/sympy/ntheory/residue_ntheory.py:36, in n_order(a, n)
     34 a, n = as_int(a), as_int(n)
     35 if igcd(a, n) != 1:
---> 36     raise ValueError("The two numbers should be relatively prime")
     37 factors = defaultdict(int)
     38 f = factorint(n)

ValueError: The two numbers should be relatively prime

n_order(3, p)

31

# Check: do these orders divide the size of the group (p-1)
(p-1)/22

31.0

(p-1)/31

22.0

# Not quite what we want
22%(p-1)

22

# Fancier way to check that 22 divides p-1, using `%`
# For example, 27%11 is 5
(p-1)%22

0

gens_list = []
for g in range(1, p):
    if n_order(g, p) == p-1:
        gens_list.append(g)

# Secretly this list has length phi(p-1), where phi(p-1) is the size of (Z/(p-1)Z)^x
print(gens_list)

[5, 6, 7, 11, 13, 15, 17, 18, 20, 21, 23, 24, 28, 31, 33, 38, 39, 41, 43, 44, 45, 47, 50, 51, 52, 54, 58, 60, 63, 68, 69, 70, 72, 73, 79, 84, 89, 92, 93, 95, 96, 98, 99, 106, 107, 110, 113, 114, 117, 118, 122, 123, 125, 129, 130, 131, 132, 133, 134, 135, 139, 141, 142, 145, 148, 149, 150, 152, 153, 154, 156, 157, 162, 164, 166, 170, 172, 174, 175, 176, 179, 180, 181, 182, 188, 189, 194, 199, 200, 202, 203, 204, 206, 207, 208, 209, 210, 216, 218, 219, 223, 230, 232, 237, 238, 242, 245, 247, 251, 252, 254, 263, 267, 271, 272, 274, 275, 276, 277, 279, 280, 283, 285, 286, 288, 294, 295, 297, 302, 305, 307, 310, 318, 319, 320, 321, 322, 323, 326, 330, 331, 334, 335, 338, 339, 343, 346, 351, 354, 355, 356, 359, 366, 368, 369, 370, 374, 375, 377, 379, 380, 382, 383, 384, 385, 387, 390, 392, 393, 394, 396, 399, 401, 402, 405, 410, 413, 415, 417, 419, 421, 422, 423, 424, 425, 426, 428, 434, 435, 437, 439, 442, 444, 447, 448, 449, 450, 452, 454, 456, 457, 458, 459, 461, 462, 463, 466, 468, 469, 470, 471, 472, 478, 485, 486, 487, 488, 491, 492, 493, 496, 497, 498, 499, 500, 505, 506, 510, 514, 515, 516, 518, 520, 522, 523, 524, 525, 528, 532, 536, 537, 539, 540, 543, 546, 547, 556, 557, 562, 563, 564, 567, 568, 574, 575, 578, 580, 581, 582, 583, 586, 589, 592, 593, 595, 596, 597, 598, 600, 601, 605, 606, 608, 609, 612, 617, 618, 621, 622, 624, 626, 627, 628, 630, 634, 635, 641, 643, 647, 648, 649, 653, 654, 657, 658, 661, 664, 669, 671, 673]

len(gens_list)

300

p-1

682

from math import gcd

# What is (Z/682Z)^x?
N = p-1
elt_list = []
for a in range(N):
    if gcd(a, N) == 1:
        elt_list.append(a)

len(elt_list)

300

print(elt_list)

[1, 3, 5, 7, 9, 13, 15, 17, 19, 21, 23, 25, 27, 29, 35, 37, 39, 41, 43, 45, 47, 49, 51, 53, 57, 59, 61, 63, 65, 67, 69, 71, 73, 75, 79, 81, 83, 85, 87, 89, 91, 95, 97, 101, 103, 105, 107, 109, 111, 113, 115, 117, 119, 123, 125, 127, 129, 131, 133, 135, 137, 139, 141, 145, 147, 149, 151, 153, 157, 159, 161, 163, 167, 169, 171, 173, 175, 177, 179, 181, 183, 185, 189, 191, 193, 195, 197, 199, 201, 203, 205, 207, 211, 213, 215, 219, 221, 223, 225, 227, 229, 233, 235, 237, 239, 241, 243, 245, 247, 249, 251, 255, 257, 259, 261, 263, 265, 267, 269, 271, 273, 277, 281, 283, 285, 287, 289, 291, 293, 295, 299, 301, 303, 305, 307, 309, 311, 313, 315, 317, 321, 323, 325, 327, 329, 331, 333, 335, 337, 339, 343, 345, 347, 349, 351, 353, 355, 357, 359, 361, 365, 367, 369, 371, 373, 375, 377, 379, 381, 383, 387, 389, 391, 393, 395, 397, 399, 401, 405, 409, 411, 413, 415, 417, 419, 421, 423, 425, 427, 431, 433, 435, 437, 439, 441, 443, 445, 447, 449, 453, 455, 457, 459, 461, 463, 467, 469, 471, 475, 477, 479, 481, 483, 485, 487, 489, 491, 493, 497, 499, 501, 503, 505, 507, 509, 511, 513, 515, 519, 521, 523, 525, 529, 531, 533, 535, 537, 541, 543, 545, 547, 549, 551, 553, 555, 557, 559, 563, 565, 567, 569, 571, 573, 575, 577, 579, 581, 585, 587, 591, 593, 595, 597, 599, 601, 603, 607, 609, 611, 613, 615, 617, 619, 621, 623, 625, 629, 631, 633, 635, 637, 639, 641, 643, 645, 647, 653, 655, 657, 659, 661, 663, 665, 667, 669, 673, 675, 677, 679, 681]

Not at all obvious why these two sizes are equal. It’s a hard Math 120A exercise to convince yourself these are the same.

Main thing to notice for now: in general, there are lots of generators. (300 of the 682 options in this case.)

In Lab 2, you don’t need to find all of the generators, you just need to find one generator.

Warning: The primes you use in Lab 2 should be much bigger than 683.

# This is still naive, still slow, but better than what I wrote in Homework 2.
def better_naive_dlog(g, h, p):
    '''This will be the first positive value x such that g^x mod p == h, if it exists'''
    y = 1 # This is g^0 mod p
    for x in range(1, p):
        # compute y = g^x mod p assuming y is currently g^(x-1) mod p
        # Could use y = pow(g, x, p), but let's take advantage of already knowing g^(x-1) mod p
        y = (y*g)%p
        if y == h:
            return x

    # If no solution exists, return None
    return None

(7**43)%101

46

better_naive_dlog(7, 46, 101)

43

n_order(5, 101)

25

pow(5, 87, 101)

92

better_naive_dlog(5, 92, 101)

12

pow(5, 12, 101)

92

pow(5, 12+25, 101)

92

pow(5, 62, 101)

92

As we’ve defined it, discrete logarithms have either 0 solutions or infinitely many solutions.

Created in deepnote.com Created in Deepnote