#Shaurya Baranwal, Homework 24 due April 21, 2024
#OK to post

#----------------------
# Important Functions |
#----------------------

#C24.txt: April 15, 2024
Help:=proc(): print(`MakeRSAkey1(K) , MakeRSAkey(K,M) `): 
print(`AliceToBob(M,Nbob,eBob,Nalice,dAlice,H)`):
print(`BobReadAlice(MS,Nbob,dBob,Nalice,eAlice,H)`):
end:
with(numtheory):
#MakeRSAkey1(K): makes a triple [N,e,d] where N,e, are public and d private
#one try
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:
#MakeRSkey(K,M): tries to make an RSA key by trying M times
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:

#Hash function: x&^3 mod H
#AliceToBob(M,Nbob,eBob,Nalice,dAlice,H):|
#Inputs Alice's message M, the [Nbob,eBob] public part of
#Bob's RSA key, the Nalice (public) and dAlice (private) of Alice's key
#and H (public Hash function x&^3 mod H
#output a pair the encrypted message, followed by the much shorter
#signature
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(MS,Nbob,dBob,Nalice,eAlice,H)
#inputs a signed message MS=[M1,S] sent from Alice,
#Nbob,dBob,Nalice, eAlice, and H outputs
#the deciphered message from Alice and also checks
#that it came from Alice and not from a bad guy
#pretending to be Alice
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(): {}: end:

#--------------------------------------------------
# Part 2 - Generalizing AliceToBob and BobToAlice |
#--------------------------------------------------

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:

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 - Birthday Message |
#----------------------------

# My birthday is 04/25/2004 so the message is then 04252004

#-------------------------------------------------------------------------------------------

# Here is my information for Dr.Z's homework this week.

# N := 741722208453803540319268247178773400187219540755637048600837667643712077137100784815902032907627202684725052133657977388430721940565969634497741991891629104756024347555919826922991511673210444430067957

# e := 468739773739813145043673147966921765247165617762303145800598594443673848897972709733443148896181442846999006871294294927232006568386142154050238811213459916690546269900022300085480318862425218862758487

# H := 161803399 (the golden ratio)

#-------------------------------------------------------------------------------------------

# The three people I had to send my information to were Pablo, Robert, and Daniel

# To Pablo, I sent the ecnrypted message and the *wrong* signature

#[105524109061242363010627690670911912642163568158074685963046954536047664021255590503738754814226220711941726505610661087204121721069654907632254986272741295858844223221251249344417767495294544431802860331448945045399273247043998455922905803281845356600813861, 77653645406905473989067270851811706614219930884466892818217204524297738991967674899932188657153486067779892878015596544656522880385220895923016728901871919610860214690517590905140795556813779458981805]

# Pablo told me my birthday and that I was not Shaurya and called the police on me

# To Robert, I sent the encrypted message and the correct signature

#[268734137854826286758240744350001017164155065785469257967695184222806271497565482082493653532781823860022838064203418935647838414720987430109672703847024583257260132598083084178731550772440890467060171839744592507200401444293633883294444624001570829876181778194496160018327647415009630713496714293957568478460842338160950115345090329910956583165361943653029220259973664702017204373467890159316526271312174814204440607606268318203020854848789057196617421289619796404918262278268653363529637904269032711480920115975071028975343564983336765562675577784552264270395268212906698856233174189455979327747332088768500149830127391356270467676829909126117925241979526336728669332405467491335416633606154935990770793837601725914842732835232605486523643346319337429307798256529814869158844115015350412572267634413398295002637207815875481377203194516166574414142837481556196973284103487842252039451125142968811068180075695231969622568221471247296398527567786364814474209478007140838879310887061781730264712057108095865486419679434566405414101179709377682108679499887573081514361783878304505212624702013137454497167047814217482453855956292380112355855601612582050671594960917867846335442789394095020885104417122491275347738594715750852790546415314, 77653645406905473989067270851811706614219930884466892818217204524297738991967674899932188657153486067779892878015596544656522880385220895923016728901871919610860214690517590905140795556813779458981805]

# To Daniel, I sent the encrypted message and the correct signature

#[877153888307098739283982846956862096286240739619932988842215018212432735000720232814576195781940686668466754049011023760317535113551614509473309523519204427262688762544541474213111362056512898943569549, 77653645406905473989067270851811706614219930884466892818217204524297738991967674899932188657153486067779892878015596544656522880385220895923016728901871919610860214690517590905140795556813779458981805]

# Daniel told me birthday and did not have to call the police to me

#-------------------------------------------------------------------------------------------

# The three people I had received a message from were Kaylee, Ryan, and Ramesh

# From Kaylee, I received her [N,e] and H

# [N,e]:=[4035983888024080397536969708582036667253587263607723015123625060834716529866762423922544098847465427880678612033900602704336336738182775982040534881865138536229591544007947586875662093720140825907716107, 3750642405947843788466274050989805761782119650171778166533453652960659249942375361081575911714279434004660635059434793439529763078502963499297797753191719411368955649886699148481101166665810948231529845]

# H := 1112621112853

# After sending in my information, she then sent the encrypted message and a signature

# MS:= [274447433836344924839896752379608091544818141847697871688795387252680749272269970581657817058396646364094453798829563668150388072202011866427606787584844890298938877152280925661094090811133907082053694, 2553918223772008722599605284622997569637924568133455467205804172580657836818386040560331391453425270796682875345071761170228217733083288042055930320131372090610366540097737427290290292236414244615850958]

# Kaylee's birthday is on 06/23/2001 (she sent me the correct signature)

# From Ryan, I received his [N,e] and H

# N := 71075675902377020867458486197834203818749099293106257635637664688979622728755658292668116928895566370183153059718888171923894963673493553436521783142977732724427348832679774391141885808373604669573610029

# e := 57135392383946585035396659334376779157093039942779214635683508412193771507019915775196000164640784831899150576752401249031618093414217219064633915664630766389233024519643408835667218028587592316709567855

# H := 2718281828459045

# After sending in my information, he then sent the encrypted message and a signature

# MS := [173058023037627761311356890819648502264632592388114854188983714246068403145630168667868575708123666631574696852759203632829491740703650875892908739642791308759679831471609289729025602405262488931970064, 49729376225437709066409992056723513644746851602579663972968371989130756295657063111303743372860165287769143556539903096962048531958651983543298591731989004359911454370213718601356448542230234861365882075]

# Ryan's birthday is on 01/22/2004 (he sent me the correct signature)

# From Ramesh, I received his [N,e] and H

# N := 492998771032216348012303910671315588317812474007825405259893840187936917019208744525628423093275302629340858968060126701236677019747851721692549675609518259263189;

# e := 410475808323463169303547359992192929450458850845412813816825646639530714768290252935518703659865743519504898128486163377063373918586974714316556294146251100364661;

# H := 7375128527775940

# After sending in my information, he then sent the encrypted message and a signature

# encrypted_msg := 2646104688833749149660252541234562379872017179870926493033504398489451168581866554137426462670428857925554038953460094839948992511771526349262078298393589102177339638070577324035748099430706609638993;

# signature := 85028621653560365903317208615198762098315125775906594348676282452457907233555317487699298001054874609841336046910253867512846756476457307933859924829579562737368;

# Ramesh's birthday is 11/10/2023, but it was the wrong signature so it wasn't Ramesh and I called the police on him