Assignment $9$: Due Fri Apr $19$th$,11$:$59$PM CST

Passwords generally have more "entropy" $($are less guessable and therefore more secure$)$ when they draw from

a larger pool of possibilities. For each requirement below, write a compact expression that gives the number of

possible distinct passwords with that requirement, and an approximation in scientific notation $($most calculators

will do this automatically.$)$

$-$The password must be some rearrangement of the letters $\{a,b,c,d,e,f,g,h,i,j,k,l\}.$ Example: ficaejbdhgkl

$-$The password must be twelve distinct lowercase letters. Example: schwartzkopf

$-$The password must be a string of $12$ characters which can each be lowercase, uppercase, one of ten digits or

one of ten symbols, duplicates allowed. Example: $$100!$Burger!

$-$The password must be twenty$-$four lowercase letters, duplicates allowed. Example: aristocratictravelagency

$-$When a site asks you to set a password $p,$ they do not $($should not!$)$ store your password in plaintext. Instead

they store $h(p),$ the hash of your password. Ideally, the function $h$ is injective, but "collisions" can occur. These

happen when there are two distinct passwords $p_1$ and $p_2$ such that $h(p_1)=h(p_2).$ Suppose the domain of $h$ is all

strings of $24$ lowercase english letters, and the codomain of $h$ is all strings of $24$ hexadecimal digits. Under this

scheme, prove that there must be at least one group of at least $100,000$ distinct passwords that all collide with each

other.Passwords generally have more $$entropy$($are less guessable and therefore more secure$)$ when they draw froma larger pool of possibilities. For each requirement below, write a compact expression that gives the number ofpossible distinct passwords with that requirement, and an approximation in scientific notation $($most calculatorswill do this automatically.$)-$The password must be some rearrangement of the letters $\{$a$,$b$,$c$,$d$,$e$,$f$,$g$,$h$,$i$,$j$,$k$,$l$\}.$ Example: ficaejbdhgkl$-$The password must be twelve distinct lowercase letters. Example: schwartzkopf$-$The password must be a string of $12$ characters which can each be lowercase, uppercase, one of ten digits orone of ten symbols, duplicates allowed. Example: $$100!$Burger!$-$The password must be twenty$-$four lowercase letters, duplicates allowed. Example: aristocratictravelagency$-$When a site asks you to set a password p$,$ they do not $($should not!$)$ store your password in plaintext. Insteadthey store h$($p$),$ the hash of your password. Ideally, the function h is injective, but $$collisions$$ can occur. Thesehappen when there are two distinct passwords p$1$ and p$2$ such that h$($p$1)=$ h$($p$2).$ Suppose the domain of h is allstrings of $24$ lowercase english letters, and the codomain of h is all strings of $24$ hexadecimal digits. Under thisscheme, prove that there must be at least one group of at least $100,000$ distinct passwords that all collide with each other.