R-ohjelmointi.org
Tilastotieteellistä ohjelmointia R-kielellä
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) } |