Klassisia salausmenetelmiä

Salakirjoitusmenetelmät ovat aina kiinnostaneet minua. Muistan, että järjestimme jo kymmenvuotiaina muutaman kaverin kanssa kilpailun, jossa piti purkaa salakielinen sanoma. Viestin salaus onnistui silloin niin hyvin, ettei sen purkaminen onnistunut käsipelillä. Muistan kyllä tajunneeni, että muut(kin) käyttivät todennäköisesti menetelmää, jossa alkuperäiset aakkoset on korvattu toisilla merkeillä. Koska salakirjoitettu viesti oli kovin lyhyt, ei sen purkaminen käyttäen suomen tunnettuja merkkitaajuuksia kuitenkaan onnistunut.

Löysin taannoin kirjakaupasta Simon Singhin kirjan The Code Book, joka tarjoaa ainakin näin erityisesti alalle kouluttautumattomalle mielenkiintoisen johdannon salakirjoitusmenetelmiin. Kirjan lopussa on myös kymmenen tehtävää, joilla voi testata osaamistaan. Mainittakoon että kaikkien kymmenen tehtävän ratkaisijalle luvattiin rahapalkinto, mutta kilpailu on ratkennut jo liki 20 vuotta sitten.

Katsahdetaanpa muutamiin klassisiin salausmenetelmiin Singhin kirjan pohjalta. En onnistunut löytämään R-kielistä toteutusta useimmista, joten alla on jonkinlainen toteutus muutamista menetelmistä.

Taustaa

Kirjan mukaan salakirjoitustekniikka voidaan tieteenalana jakaa kahteen haaraan: steganografiaan eli tiedon piilottamiseen ja kryptologiaan eli tiedon salaamiseen.

Substuutiomenetelmät

Vanhimpia salaustekniikoita ovat muun muassa Atbash- ja Caesar-salakirjoitus. Molemmat perustuvat ajatukseen, jossa viestin merkit korvataan jollakin toisella merkillä (substituutio). Atbash-salakirjoituksessa merkistön ensimmäinen kirjain korvataan merkistön viimeisellä kirjaimelle, toinen kirjain toiseksi viimeisellä ja niin edelleen, jolloin alkuperäisestä a-kirjaimesta tuleekin ö, b:stä ä, jne., siis näin:

alkup.: abcdefghijklmnopqrstuxyzåäö
viesti: öäåzyxutsrqponmlkjihgfedcba

Caesar-salakirjoituksessa (shift cipher) merkistöä siirretään k-merkkiä eteenpäin. Esimerkiksi siirrettäessä merkistöä kolme kirjainta eteenpäin, tulee alkuperäisestä a:sta d. Koodiavain näyttäisi siis tässä tapauksessa seuraavalta, koska merkistön loppuun päästessä kierretään aloittamaan alusta:

alkup.: abcdefghijklmnopqrstuxyzåäö
viesti: åäöabcdefghijklmnopqrstuxyz

Molemmat salakirjoitukset toimivat aikanaan hyvin, mutta nykyisin ne ovat heikkoja, ja aukeavat tietokoneella varsin helposti. Etenkin jos viesti on vähänkään pidempi ja jos kielikin tunnetaan, voidaan salakirjoitus avata tutkimmalla kaikki mahdolliset avaimet. Caesar-salausta voidaan vahvistaa sallimalla minkä tahansa alkuperäisen kirjaimen vastata mitä hyvänsä toista kirjainta (alla vain ”substitution cipher”). Tämäkin salaus kuitenkin aukeaa frekvenssianalyysillä, etenkin jos kieli tunnetaan.

Transpositiomenetelmät

Edellä mainittujen substituutiomenetelmien lisäksi voidaan käyttää myös transpositiomenetelmiä, joissa alkuperäisen viestin kirjainten järjestystä muutetaan siten, että viestistä muodostuu alkuperäisen tekstin anagrammi. Eräs yksinkertainen transpositiomenetelmä on rail fence, jossa kirjaimet kirjoitetaan vuorotellen eri riveille, ja salakirjoitettu viesti muodostuu rivi kerrallaan.

R-kieliset esimerkit

Katsotaanpa miten tämän kirjoituksen lopussa olevilla funktioilla voidaan muodostaa salakielisiä sanomia.

Rail fence

text <- "Aluksi kirjoitettujen viestien harvinaisuus suojasi viestejä."
 
rail <- paste(encrypt_railfence(text), collapse="")
rail
#[1] "Aus ijietjnvete avniussoaivetj.lkikrottue isinhriasu ujs iseä"
 
orig <- paste(decrypt_railfence(rail), collapse="")
orig
#[1] "Aluksi kirjoitettujen viestien harvinaisuus suojasi viestejä."

Atbash

text <- "Aluksi kirjoitettujen viestien harvinaisuus suojasi viestejä."
 
atbash <- paste(encrypt_atbash(text), collapse="")
atbash
#[1] "örisku sultoujyjjityp huykjuyp völhupöukiik kiotöku huykjytb."
 
orig <- paste(decrypt_atbash(atbash), collapse="")
orig
#[1] "aluksi kirjoitettujen viestien harvinaisuus suojasi viestejä."

Caesar

text <- "Aluksi kirjoitettujen viestien harvinaisuus suojasi viestejä."
 
caesar <- paste(encrypt_caesar2(text, code="d"), collapse="")
caesar
#[1] "doxnvl nlumrlwhwwxmhq ylhvwlhq kduylqdlvxxv vxrmdvl ylhvwhmb."
 
orig <- paste(decrypt_caesar2(caesar, code="d"), collapse="")
orig
#[1] "aluksi kirjoitettujen viestien harvinaisuus suojasi viestejä."

Substituutio

text <- "Aluksi kirjoitettujen viestien harvinaisuus suojasi viestejä."
 
sub <- paste(subst_encrypt(text, 5), collapse="")
sub
#[1] [1] "5fijögu öukådupcppjåcv wucgpucv rfkwuvfugjjg gjdåfgu wucgpcån."
 
orig <- paste(subst_decrypt(sub), collapse="")
orig
#[1] "aluksi kirjoitettujen viestien harvinaisuus suojasi viestejä."

Toteutus R:llä

Seuraavassa on muutamia R-kielisiä toteutuksia erilaisista menetelmistä. Näiden toteutus ei ole millään lailla optimaalinen, eikä niiden turvallisuuteen kannata perustaa mitään oikeita sovelluksia.

Substituutiomenetelmät

Atbash

# Atbash cipher
encrypt_atbash <- function(text, let=NULL) {
   if(is.null(let)) {
      let  <- c(letters, "å", "ä", "ö")
   }
   let2 <- paste(let, collapse="")
   let3 <- paste(rev(let), collapse="")
   cipher <- function(x) {
      chartr(let2, let3, x)
   }
   text2 <- tolower(strsplit(text, "")[[1]])
   res <- cipher(text2)
   return(res)
}
 
decrypt_atbash <- function(text, let=NULL) {
   if(is.null(let)) {
      let  <- c(letters, "å", "ä", "ö")
   }
   let2 <- paste(let, collapse="")
   let3 <- paste(rev(let), collapse="")
   cipher <- function(x) {
      chartr(let2, let3, x)
   }
   text2 <- tolower(strsplit(text, "")[[1]])
   res <- cipher(text2)
   return(res)
}

Caesar

# Allows one to specify the alphabets
encrypt_caesar2 <- function(text, code, let=NULL) {
   if(is.null(let)) {
      let  <- c(letters, "å", "ä", "ö")
   }
   ind0 <- which(let == code)
   ind1 <- ind0:length(let)
   if(ind0 != 1) {
      ind2 <- 1:(ind0-1)
   } else {
      ind2 <- NA
   }
   ind  <- as.vector(na.omit(c(ind1, ind2)))
 
   let2 <- paste(let, collapse="")
   let3 <- paste(let[ind], collapse="")
 
   cipher <- function(x) {
      chartr(let2, let3, x)
   }
 
   text2 <- tolower(strsplit(text, "")[[1]])
 
   res <- cipher(text2)
   return(res)
}
 
decrypt_caesar2 <- function(text, code, let=NULL) {
   if(is.null(let)) {
      let  <- c(letters, "å", "ä", "ö")
   }
   ind0 <- which(let == code)
   ind1 <- ind0:length(let)
   if(ind0 != 1) {
      ind2 <- 1:(ind0-1)
   } else {
      ind2 <- NA
   }
   ind  <- as.vector(na.omit(c(ind1, ind2)))
 
   let2 <- paste(let, collapse="")
   let3 <- paste(let[ind], collapse="")
 
   cipher <- function(x) {
      chartr(let3, let2, x)
   }
 
   text2 <- tolower(strsplit(text, "")[[1]])
 
   res <- cipher(text2)
   return(res)
}

Substituutioavain

# Substitution cipher
subst_encrypt <- function(text, seed, let=NULL) {
   if(is.null(let)) {
      let  <- c(letters, "å", "ä", "ö")
   }
   let2 <- paste(let, collapse="")
 
   set.seed(seed)
   ind <- sample(1:length(let), length(let))
   let3 <- paste(let[ind], collapse="")
 
   cipher <- function(x) {
      chartr(let2, let3, x)
   }
 
   text2 <- tolower(strsplit(text, "")[[1]])
 
   res <- cipher(text2)
   res <- c(seed, res)
   return(res)
}
 
subst_decrypt <- function(text, let=NULL) {
   if(is.null(let)) {
      let  <- c(letters, "å", "ä", "ö")
   }
   let2 <- paste(let, collapse="")
 
   seed<-strsplit(text, "")[[1]][1]
 
   set.seed(as.numeric(seed))
   ind <- sample(1:length(let), length(let))
   let3 <- paste(let[ind], collapse="")
 
   cipher <- function(x) {
      chartr(let3, let2, x)
   }
 
   text2 <- tolower(strsplit(text, "")[[1]])
 
   res <- cipher(text2)[-1]
   return(res)
}

Transpositiomenetelmät

Rail fence

 
encrypt_railfence <- function(text) {
   text2 <- (strsplit(text, "")[[1]])
 
   ind1 <- seq(1, length(text2), by =2)
   ind2 <- seq(2, length(text2), by =2)
 
   res <- c(text2[ind1], text2[ind2])
   return(res)
}
 
decrypt_railfence <- function(text) {
   text2 <- (strsplit(text, "")[[1]])
 
   ind1 <- seq(1, length(text2), by =2)
   ind2 <- seq(2, length(text2), by =2)
 
   res <- text2[order(c(ind1, ind2))]
   return(res)
}

Kryptoneliö

# Crypto square
encrypt_square <- function(text) {
 
   text2 <- gsub("[[:punct:]]|[[:space:]]", "", text)
   text3 <- strsplit(text2, "")[[1]]
 
   side <- sqrt(length(text3))
   col <- ceiling(side)
   row <- floor(side)   
 
   max.len <- col * row
   length(text3) <- max.len
   text3[is.na(text3)]<-""
 
   m <- matrix(ncol=col, nrow=row, data=tolower(text3), byrow=TRUE)
 
   res <- paste(apply(m, 2, function(x) paste(x, collapse="")), collapse=" ")
   return(res)
}
 
decrypt_square <- function(text) {
   text2 <- unlist(strsplit(strsplit(text, " ")[[1]], ""))
 
   side <- sqrt(length(text2))
   col <- ceiling(side)
   row <- floor(side)   
 
   text2 <- (strsplit(text, " ")[[1]])
 
   max.len <- max(nchar(text2))
   text3<-strsplit(paste(formatC(text2, width=max.len, format="s", flag="-"), collapse=""), "")[[1]]
 
   max.len <- col * row
   length(text3) <- max.len
   text3[is.na(text3)]<-""
 
   m <- matrix(ncol=col, nrow=row, data=tolower(text3), byrow=FALSE)
   res <- paste(apply(m, 1, function(x) paste(x, collapse="")), collapse=" ")
 
   return(res)
}

R-ohjelmointi.org

Tilastotieteellistä ohjelmointia R-kielellä