Kombinatorikk for passord

Kombinatorikk for passord

En skole har regler for å lage passord.

Regelsett 1

  • Passordet må ha nøyaktig 6 tegn.
  • Det er bare lov å bruke store og små bokstaver.
  • Det må være minst én stor bokstav i passordet.
  • Det må være minst én liten bokstav i passordet.

Hvor mange forskjellige passord er det mulig å lage ved å følge regelsett 1?

Skolen vil øke sikkerheten og legger til flere krav for å lage passord. De lager et nytt sett med regler.

Regelsett 2

  • Passordet må ha nøyaktig 6 tegn.
  • Det må være nøyaktig to store bokstaver i passordet.
  • Det må være nøyaktig to små bokstaver i passordet.
  • Det må være nøyaktig to sifre i passordet.

Gjør nødvendige beregninger for å vurdere effekten på sikkerheten av regelsett 2.

Fasit

5862296=3687904590258^{6}-2 \cdot 29^{6}= 36\,879\,045\,902 ulike passord (ca. 36,9 milliarder).

63655290006\,365\,529\,000 ulike passord. Regelsett 2 gir dårligere sikkerhet enn regelsett 1.

Løsningsforslag
  • Passordet må ha 6 tegn
  • Kun store og små bokstaver
  • Minst 1 stor bokstav
  • Minst 1 liten bokstav

Det er 29 små bokstaver og 29 store bokstaver, dette gir i utgangspunktet 58 ulike muligheter for hver av de 6 tegnene i passordet. Dersom vi ikke hadde hatt kravene om minst 1 liten og stor bokstav ville antallet kombinasjoner derfor ha vært 58658^{6}.

Siden vi må minst ha 1 liten bokstav så kan vi ta bort de kombinasjonene som bare bruker store bokstaver (29629^6) og de som bare bruker små bokstaver (29629^6). Til sammen har vi da

586296296=5862296=36 879 045 90258^6-29^6-29^6=58^6-2 \cdot 29^6=36 \, 879 \, 045 \, 902

Det er 36,9 milliarder ulike passordet ifølge dette regelsettet.

Det finnes fremdeles 29 ulike store bokstaver, 29 ulike små bokstaver og det finnes 10 ulike siffer.

Hvis rekkefølgen ikke hadde spilt noen rolle ville vi fått 292292102=70 728 10029^{2}\cdot 29^{2} \cdot 10^{2}=70\, 728\, 100 kombinasjoner.

Rekkefølgen på de ulike tegnene spiller en rolle, siden vi har 6 tegn («ledige plasser») og skal plassere 3 ×\times 2 ulike typer tegn så kan vi finne antallet permutasjoner med

6!2!2!2!=7208=90\frac{6!}{2!\cdot 2! \cdot 2!}=\frac{720}{8}=90

Det finnes altså 70 728 10090=6 365 529 00070\, 728\, 100 \cdot 90=6\, 365\, 529\, 000 ulike passord.

Det finnes omtrent 6 ganger så mange mulige passord med regelsett 1 som med regelsett 2. Regelsett 2 vil derfor sannsynligvis gjøre sikkerheten en god del dårligere enn regelsett 1.