Sage and Diffie-HellmanWith the Diffie-Hellman method, Bob and Alice agree on a base generator (\g\)) and a large random prime number (\(n\)). Bob then generators a random value (\(b\)) which is between 0 and \(n-1\), and Alice does the same (\(a\)). Bob computes \(B=g^b \pmod n\) and Alice computes \(A=g^a \pmod n\). They exchange these values, and Bob generates the shared secret as \(K_b=A^b \pmod n\) and Alice generates with \(K_a=B^a \pmod n\). TheoryWith the Diffie-Hellman method, Bob and Alice agree on a base generator (\(g\)) and a large random prime number (\(n\)). Bob then generators a random value (\(b\)) which is between 0 and \(n-1\), and Alice does the same (\(a\)). Bob computes: \(B=g^b \pmod n\) and Alice computes: \(A=g^a \pmod n\) They exchange these values, and Bob generates the shared secret as: \(K_b=A^b \pmod n\) and Alice generates with: \(K_a=B^a \pmod n\). CodingIn Sage, we can create a ring of integers modulo of \(n\) with: ZZn = IntegerModRing(n) This is now the set of integers from 0 to \(n-1\). The following defines the Sage code: n = random_prime(2^512) ZZn = IntegerModRing(n) g= ZZn (3) a = ZZn.random_element() b = ZZn.random_element() A = g^a B = g^b Key1= A^b Key2= B^a print (f"n={n}") print (f"a={a}, b={b}") print (f"A={A}, B={B}") print (f"Key1={Key1}, Key2={Key2}") print (Key2 == Key1) and a sample run for a 512-bit prime number is: n=12291706709855557186205798290720237781042348342629033784772290434133088471826846361745430931876461861587980776420301693246933535535464097992687222397029451 a=629928845433560324411151753137612356056859894663151811304034845844513523040853151308218472224270739006157930972096508169437045905224091715362023210685030, b=5486537881409827399907001894471684530588182049663264961443135687136744876433674107049796727530405220138529268321456270641578694727727278934031899429540792 A=1707659396793396736066005913930826874905733553997696471873103720049447933647724524704775253639970290672677087820663251715792964359922695003913433504022645, B=2933287943581749097839139730831406997859611612862513536824621457282096070072355314080878109830128602654827918524873152019749554508627232160280830422874835 Key1=4048669883436329874007942617945810984441533527643395902618933082177197952434805147883268158764370864002029589364121821743692178523369217553607768354315504, Key2=4048669883436329874007942617945810984441533527643395902618933082177197952434805147883268158764370864002029589364121821743692178523369217553607768354315504 True If we modify with a 256-bit prime number: n = random_prime(2^256) and a sample run is: n=66551304783105610638443160167503754927854108040707193674043881939645513014499 a=49696657784210335987700734097162770686718694604884140139173319399570624097267, b=37051738095974167582475601344903302764029818440366671438821051631632478962831 A=13043599396268610542598008577755784289195454675167421313701199599272235713720, B=59453809134529254664025476129978825231518158859688344388286238411281364656263 Key1=54611148873087437583507407286281007548570528369574681353278628546741634204010, Key2=54611148873087437583507407286281007548570528369574681353278628546741634204010 True |