Thank Fermat For Your Online Security

Thank Fermat For Your Online Security

You might not know it, but Pierre de Fermat — a lawyer and mathematician — created a little theorem that makes sure that the Web site that you connect to is the right one. With this, when you connect to a Web site, the site provides its public key and signs a message with the associated private key. Your browser will then check the signature against the public key, ad if it checks out, you will be allowed to connect to the Web site. Otherwise, these days, the browser will give you a warning that the site cannot be trusted. It is crypto magic!

While elliptic curve cryptography is typically used for the key exchange method these days (such as with ECDH — Elliptic Curve Diffie Hellman), it is normally RSA that is used to provide the public key and create the signature.

Most people think it was Leonhard Euler who helped solve the puzzle of finding a trapdoor in public key encryption. But, it was actually Fermat’s Little Theorem which provided the solution to the problem [here]:

With Fermat’s Little Theorem, we have:

and where p is a prime number. The basic method for encrypting and also signing is [here]:

The coding is here:

from Crypto.Util.number import *
from Crypto import Random
import Crypto
import sys

bits=256

val=10

if (len(sys.argv)>1):
    val=int(sys.argv[1])
if (len(sys.argv)>2):
    bits=int(sys.argv[2])

p = Crypto.Util.number.getPrime(bits, randfunc=Crypto.Random.get_random_bytes)
q = Crypto.Util.number.getPrime(bits, randfunc=Crypto.Random.get_random_bytes)
PHI=(p-1)*(q-1)
N=p*q
e=65537
d=pow(e,-1,PHI)

cipher=pow(val,e,N)
val_recovered=pow(cipher,d,N)

print(f"p={p}")
print(f"q={q}")
print(f"N={N}")
print(f"e={e}")
print(f"d={d}")
print(f"\nValue: {val}")
print(f"Cipher: {cipher}")
print(f"Recovered: {val_recovered}")

sign=pow(val,d,N)
sig_check=pow(sign,e,N)

print(f"\nSignature: {sign}")
print(f"Recovered: {sig_check}")

A sample run with 8-bit prime numbers gives [here]:

p=835356023750368583
q=975905667006792017
N=815228677546245045802824768172001911
e=65537
d=547710970917782558432526875835831329

Value: 5
Cipher: 206709065055587049834163257881172622
Recovered: 5

Signature: 168734520236506073217407906773331737
Recovered: 5

And for 256-bit prime numbers:

p=99669309184964400440504148254640449387921690660930870178296497668555301000603
q=57930652729616565417103100681210401913984469851405963481488399827270140348329
N=5773908138194955359336545917584001758171243367947895501855870635425004862216342240586766397216423047235637919773055800672742983543694697498183336659042387
e=65537
d=3371732583988573425044920408499890615789121487628880002922410624354950044736188754159538945324402855695730272665890158183584525996608726980803389563335921

Value: 5
Cipher: 1229826776066900660516079967053574295928939403219863737298228301668838946309218873110371629666522225939735619217869784371884330481433421998020544924300638
Recovered: 5

Signature: 3653647724144190406016605959207960859032603810862319661802368100450180437409840924169605757636691014869158166324809165207584828959710360673073880091615591
Recovered: 5

Normally, these days, we need prime numbers that are greater than 1,024 bits, and which give a 2048-bit modulus. So, thank Fermat for your on-line security. Go try it here:

https://asecuritysite.com/rsa/rsa_full

References

Rivest, R. L., Shamir, A., & Adleman, L. (1978). A method for obtaining digital signatures and public-key cryptosystems. Communications of the ACM, 21(2), 120–126.