# OK to post homework
# Alex Varjabedian, 15-Apr-2024, Homework 24

Help := proc() print(`fieldTrip()\nAliceToBobG(ListM,Nbob,eBob,Nalice,dAlice,H)\nBobReadAliceG(MS,Nbob,dBob,Nalice,eAlice,H)`) end:

MakeRSAkey1:=proc(K) local P,Q,ra,N,e,d:
ra:=rand(10^K..10^(K+1)):
P:=nextprime(ra()):
Q:=nextprime(ra()):
if P=Q then
 RETURN(FAIL):
fi:
N:=P*Q:
e:=rand(1..(P-1)*(Q-1))():
if gcd(e,(P-1)*(Q-1))<>1 then
  RETURN(FAIL):
fi:
d:=e&^(-1) mod (P-1)*(Q-1):
[N,e,d]:
end:

MakeRSAkey:=proc(K,M)  local m,rsa:
for m from 1 to M do
rsa:=MakeRSAkey1(K):
 if rsa<>FAIL then
   RETURN(rsa):
 fi:
od:
FAIL:
end:

AliceToBob:=proc(M,Nbob,eBob,Nalice,dAlice,H) local x,M1,S:
M1:=M&^eBob mod Nbob:
x:=M&^3 mod H:
S:=x&^dAlice mod Nalice:
[M1,S]:
end:

BobReadAlice:=proc(MS,Nbob,dBob,Nalice,eAlice,H) local M1,S,M,X,X1:
M1:=MS[1]:
S:=MS[2]:
M:=M1&^dBob mod Nbob:
X:=M&^3 mod H:
X1:=S&^eAlice mod Nalice:
if X<>X1 then
 print(`You are not Alice, I will call the police`):
fi:
M:
end:

#######################
# ------------------- #
# PART 1 - Field Trip #
# ------------------- #
#######################

fieldTrip := proc() return {} end:

# Running fieldTrip()
printf("Field trip days: %a\n", fieldTrip());

######################################################################################################
# -------------------------------------------------------------------------------------------------- #
# PART 2 - AliceToBobG(ListM,Nbob,eBob,Nalice,dAlice,H), BobReadAliceG(MS,Nbob,dBob,Nalice,eAlice,H) #
# -------------------------------------------------------------------------------------------------- #
######################################################################################################

# Returns a list containing a list of encrypted messages, and the signature
AliceToBobG := proc(ListM,Nbob,eBob,Nalice,dAlice,H) local x, M1, S, M:
M1:=[seq(M&^eBob mod Nbob, M in ListM)]:
S:=add((M&^3 mod H)&^dAlice mod Nalice, M in ListM):
[M1,S]:
end:

# Returns a list of decrypted messages
BobReadAliceG := proc(MS,Nbob,dBob,Nalice,eAlice,H) local M1, S, M, X, X1, M2, M3, i:
M1:=MS[1]:
S:=MS[2]:
M:=[seq(M2&^dBob mod Nbob, M2 in M1)]:
X:=[seq(M3&^3 mod H, M3 in M)]:
X1:=S&^eAlice mod Nalice:
for i from 1 to nops(X) do
 if X[i]<>X1 then print(`You are not Alice, I will call the police`) fi:
od:
M:
end:

#####################
# ----------------- #
# PART 3 - Emailing #
# ----------------- #
#####################

(*
Using MakeRSAkey, I generated the following result:
[N, e, d] = [
127711530576913131575822837202695013403663973620035921837879420367037214508135409563566908342874207064840127385407221751352663779327696096399630613900936616858959749861340170876488836082629813856249120005724484735689838811034360372512307576472640677385363361607178937414342488091713518463212893445678420981681836444012003107363190609806803250295744593107767353636904574968104745778336591373948331356757
,
119355774480941089068182500865657768029894607347642880120545383004726786851010456573815590351368205648404734577585495922417424364163563086225199220958858935794581522185774723052024382414153458927245099731963599373227019468645772411467935611447961466163613435976492179213526206037862087594104175657308096047213419047678857605794783582772159597837949854191484531513184753882102313617780747286231266988359
,
80795571055657990107115625398799989476101446646439325110488524349891475045823737457920242597643855198436848655679494794447668055760712125038529894871778106965873081077483622114885464688166194828972377676816748130118601350094523628104375526789307932630130213438871980501247611700725006797191643101717057469220436175201055384261809435091652513420569104468506229762354846523800841170500646804955348923987
]
Let H(M) = M^3 mod 314159265358979
My birthday is July 26, 2004, which becomes 07262004.

To Kaylee:
She sent me
N = 4035983888024080397536969708582036667253587263607723015123625060834716529866762423922544098847465427880678612033900602704336336738182775982040534881865138536229591544007947586875662093720140825907716107
e = 3750642405947843788466274050989805761782119650171778166533453652960659249942375361081575911714279434004660635059434793439529763078502963499297797753191719411368955649886699148481101166665810948231529845
After encrypting, I sent her
[13703738463598082819288408972333011713813609682168060757800801985698162468112531653473719359047604688153875979164492784164173302013496220395908688926334790058712924038954682506935555645131477559979036, 41609026479294837627479040188604183676706517652713839057652443887342692678954624305700318979296270980927726623549771140445052057937492271849641146238280090203244127976822264355785360677605339066707010492776280361313633030101445841691117063079012558329841541755025176338600638857796823113475423963217106573127434668503031109280218558061636941883972776171843938002201889898764993236191090615358517167694]
She sent me my correct birthday and verified that the message came from me.

To Ryan:
He sent me
N = 71075675902377020867458486197834203818749099293106257635637664688979622728755658292668116928895566370183153059718888171923894963673493553436521783142977732724427348832679774391141885808373604669573610029
e = 57135392383946585035396659334376779157093039942779214635683508412193771507019915775196000164640784831899150576752401249031618093414217219064633915664630766389233024519643408835667218028587592316709567855
After encrypting, I sent him
[15003425929777340328572846898040234443276518776018216465292452870982235421430045913480372267119068651687573902701485005189336667562868844629242584276010727220770466183803164082006526380551567524290539551, 41609026479294837627479040188604183676706517652713839057652443887342692678954624305700318979296270980927726623549771140445052057937492271849641146238280090203244127976822264355785360677605339066707010492776280361313633030101445841691117063079012558329841541755025176338600638857796823113475423963217106573127434668503031109280218558061636941883972776171843938002201889898764993236191090615358517167694]
He sent me my correct birthday and verified that the message came from me.

To Ramesh:
He sent me
N = 492998771032216348012303910671315588317812474007825405259893840187936917019208744525628423093275302629340858968060126701236677019747851721692549675609518259263189
e = 410475808323463169303547359992192929450458850845412813816825646639530714768290252935518703659865743519504898128486163377063373918586974714316556294146251100364661
After encrypting, the result was
[389593594106218059695031631198633639149383428551282129657546146819332478859246814718509308771282595402974694377358953428959173519046166567274755532977894618412556, 41609026479294837627479040188604183676706517652713839057652443887342692678954624305700318979296270980927726623549771140445052057937492271849641146238280090203244127976822264355785360677605339066707010492776280361313633030101445841691117063079012558329841541755025176338600638857796823113475423963217106573127434668503031109280218558061636941883972776171843938002201889898764993236191090615358517167694]
but I decided to sign it incorrectly by replacing the last digit with a 5, so I sent him
[389593594106218059695031631198633639149383428551282129657546146819332478859246814718509308771282595402974694377358953428959173519046166567274755532977894618412556, 41609026479294837627479040188604183676706517652713839057652443887342692678954624305700318979296270980927726623549771140445052057937492271849641146238280090203244127976822264355785360677605339066707010492776280361313633030101445841691117063079012558329841541755025176338600638857796823113475423963217106573127434668503031109280218558061636941883972776171843938002201889898764993236191090615358517167695]
He sent me my correct birthday and expressed his suspicions about the identity of the message sender.

From Alex Valentino:

From George:

From Lucy:

*)