Реализация алгоритма шифрования DES
Содержание
Меня всегда занимала криптография, задолго до того как я стал интересоваться программированием. Это своего рода проявление свободы в сети. Я тверждо убежден что никто ни под какими предлогами не имеет право на доступ к вашим данным, это путь мрака и тоталитаризма.
Вместе с тем я всегда думал что криптография для меня сложна и недостежима (разумеется рот13 в расчет не идет, тут все тривиально). Однако DES оказался достаточно простым в понимании (и чуть более сложным в реализации, но это уже моя оплошность). Шифрование является симметричным, т.е. ключ который шифрует данные их же и расшифровывает.
Моя имплементация алгоритма была реализована на языке Go, на основе описания с
Итак, первый пункт википедии описывает уже саму схему алгоритма, я использовал шифрование текста. Поэтому перед тем как начать писать сам код я использовал небольшой конструктор, который делал ровно следующее:
- Приводим текст к размерности кратной 64 байта. (Можно дополнить просто 0, для шифрования текста я дополнял пробелами в конце, возможно это снижает криптоустойчивость, однако функцию расширения достаточно просто изменить, к тому же алгоритм лишь для обучения, оставляю так)
- Преобразуем ключ 56 бит в 64 бита.Каким образом? Дополняем каждый 8 бит 0 или 1, с тем условием что добавочный бит должен делать кол-во единиц в байте нечетным.
Итак, из всего вышеперечисленного, на старте имеем, структуру данных, назовем ее des, конструктор для инициализации дополняющий текст и ключ. Также хочу отметить 2 добавочные функции, viewBytesAsBits и viewBitsAsBytes. Думаю из название понятно для чего, и все же под катом пояснение.
Дело в том что в работе алгоритма очень много таблиц, с которыми очень удобно общаться через индексы. Однако напрямую обратиться к номеру бита по индексу байта нельзя. Было бы неплохо если бы был слой абстракции который позволял делать это. У меня было 2 идеи, 1 написать функции которые по индексу возвращают номер бита, сложность заключалось в том что нужно каждый раз считать какой это байт по счету.
Я немного упростил, привел все биты к байтам и при дешифровании делал обратную операцию. Это значительно снижает производительность, однако упрощает работу. Я не ставил цель сделать реализцию которой можно будет пользоваться, все исключительно в образовательных целях.
Выглядит это так:
type Crypto interface {
Encrypt() (string, error)
Decrypt() (string, error)
}
type des struct {
text string
key [64]byte
}
func NewDes(text, key string) (Crypto, error) {
/*
Собственно сам конструктор, проверят ключ и строку на пустое значение,
дополняет строку и приводит ключ к 64 битному виду.
*/
if isEmpty(text) || isEmpty(key) {
return nil, emptyStringError()
}
var rawText Crypto
convertedKey := getInitialKey(key)
text = tryExpandText(text)
rawText = &des{text: text, key: convertedKey}
return rawText, nil
}
func isEmpty(text string) bool {
return len(text) <= 0
}
func emptyStringError() error {
err := errors.New("String is empty")
return err
}
func getInitialKey(key string) [64]byte {
byteKey := []byte(key)
byteKey = viewBitsAsBytes(byteKey)
var convertedKey [56]byte
copy(convertedKey[:], byteKey)
extendedKey := generateOddBitKey(convertedKey)
return extendedKey
}
func tryExpandText(text string) string {
for len(text)%8 != 0 {
text += " "
}
return text
}
Также я добавил интерфейс Crypto на случай если я буду реализовывать другие алгоритмы.
Реализация #
Данные шифруются кусками по 8 байт (64 бита) в моем случае это константа encryptBlockSize. Поэтому итерируем по входным данным с этой последовательностью.
func (s *des) Encrypt() (string, error) {
steps := len(s.text) / encryptBlockSize
encryptedBytes := []byte{}
for step := 0; step < steps; step++ {
sliceOfText := s.text[step*encryptBlockSize : encryptBlockSize*step+encryptBlockSize]
encryptedChunk := encryptByChunk([]byte(sliceOfText), s.key)
encryptedBytes = append(encryptedBytes, encryptedChunk...)
}
encryptedBits := viewBytesAsBits(encryptedBytes)
return string(encryptedBits), nil
}
Далее в функции encryptByChunk выполняется алгоритм описанный в википедии.
func encryptByChunk(chunk []byte, key [64]byte) []byte {
bits := viewBitsAsBytes(chunk)
var bitsArr [64]byte
copy(bitsArr[:], bits)
startPermutation := startPermutation(bitsArr)
encryptedData := encryptCycle(startPermutation, key)
return encryptedData[:]
}
1 пунктом мы делаем стартовую перестановку, она весьма проста, биты перемешиваются согласно таблице 1.
func startPermutation(chunk [64]byte) [64]byte {
permutatedChunk := [64]byte{}
for i := range startPermutationPositions {
permutatedChunk[i] = chunk[startPermutationPositions[i]-1]
}
return permutatedChunk
}
После чего полученная последовательность отправляется в функцию представляющую собой 16 циклов шифрования через функцию Фейстеля.
По окончании всех преобразований, вернувшись из 16 циклов мы делаем финальную перестановку, также достаточно тривиальную.
func lastPermutation(encryptedBytes [64]byte) [64]byte {
var permutatedBytes [64]byte
for i, val := range lastPermutationPositions {
permutatedBytes[i] = encryptedBytes[val-1]
}
return permutatedBytes
}
Рассмотрим цикл 16 преобразований подробнее:
func encryptCycle(bytesBlock, key [64]byte) [64]byte {
var r [32]byte
var l [32]byte
var tmp [32]byte
copy(r[:], bytesBlock[0:32])
copy(l[:], bytesBlock[32:64])
for i := 0; i < 16; i++ {
kIter := generate48BitKey(key, encryptShiftingPositions, i)
tmp = l
l = r
r = bytesXor(tmp, convertByFestel(r, kIter))
}
Функция bytesXor также описана во вспомогательных функциях к алгоритму.
Преобразования выполняются по формулам:
$L_i=R_{i-1}$
$\R_i=L_{i-1} \oplus f(R_{i-1}, K_i)$
Для каждой итерации генерируются свой уникальный ключ с помощью функции generate48BitKey:
func generate48BitKey(extendedKey [64]byte, sequence []byte, i int) [48]byte {
var round64key [64]byte
for i, val := range extendKeyPositionsC {
round64key[i] = extendedKey[val-1]
}
shiftedKey := cycleLeftShift(extendedKey, sequence[i])
for i, val := range extendKeyPositionsD {
round64key[i+32] = shiftedKey[val-1]
}
var key [48]byte
key = getFinalRoundKey(round64key)
return key
}
Ключ генерируется сдвигом с помощью таблиц decryptShiftingPositions и encryptShiftingPositions передаваемых в качестве 2 аргумента. Как указано в википедии часть байт берется перестановкой из таблицы C, часть из таблицы D. Данные берутся из одноименных массивов файла constants. В финале процедуры выполняется еще 1 перестановка бит, генерирующая 48 битный ключ из 64ех полученных.
func getFinalRoundKey(roundKey [64]byte) [48]byte {
var finalRoundKey [48]byte
for i, val := range finalKeyRoundPermutationPosisitions {
finalRoundKey[i] = roundKey[val-1]
}
return finalRoundKey
}
После всех преобразованый мы передаем ключ, а также Ri-1 в функцию фейстеля, она имеет ключевое значение:
func convertByFestel(cryptedBits [32]byte, key [48]byte) [32]byte {
extendedCryptedBits := permutatePreFestel(cryptedBits)
for i, val := range extendedCryptedBits {
extendedCryptedBits[i] = val ^ key[i]
}
var festelResult []byte
for i := 0; i < 8; i++ {
bits := extendedCryptedBits[i*6 : 6*i+6]
row := getNumberFromPseudoBits([]byte{bits[0], bits[len(bits)-1]})
col := getNumberFromPseudoBits(bits[1 : len(bits)-1])
festelResult = append(festelResult, getPseudoBitsFromNumber(byte(sBlocks[i][row][col]))...)
}
var bBlocks [32]byte
copy(bBlocks[:], festelResult)
res := permutateFestelResult(bBlocks)
return res
}
Перед использованием функции также происходит первичная перестановка. Для этого используется функция permutatePreFestel. Делающая банальную перестановку.
func permutatePreFestel(vector [32]byte) [48]byte {
var externedVector [48]byte
for i, val := range extenssionTablePositionsE {
externedVector[i] = vector[val-1]
}
return externedVector
}
Тут также используются 2 внешние функции getNumberFromPseudoBits и getPseudoBitsFromNumber. Т.к. в алгоритме нам необходимо получить блоки Bi по 6 байт каждый и затем крайние байты преобразовать в число являющиеся строкой таблицы S блоков, а центральные, также после преобразования в число интерпретировать как колонку S блоков. В контексте программы одноименная таблица sBlocks.
Далее получив значения колонки и строки вынимаем значение на их пересечении, преобразовываем в биты и помещаяем в результирующий массив. По окончании 8 итераций производим еще 1 перестановку с помощью функции permutateFestelResult.
func permutatePreFestel(vector [32]byte) [48]byte {
var externedVector [48]byte
for i, val := range extenssionTablePositionsE {
externedVector[i] = vector[val-1]
}
return externedVector
}
Расшифровывание. #
Все происходит в обратной последовательности, исключение составляется цикл из 16 преобразований, он выполняется в обратном порядке. Также сдвиг при генерации 48 битного ключа происходит по таблице 9. (все таблцы пронумерованы в константах)
func (s *des) Decrypt() (string, error) {
steps := len(s.text) / encryptBlockSize
decryptedBytes := []byte{}
bytesText := []byte(s.text)
var arrOfTextBytes [64]byte
for i := 0; i < steps; i++ {
sliceOfText := bytesText[i*encryptBlockSize : encryptBlockSize*i+encryptBlockSize]
pseudoBits := viewBitsAsBytes([]byte(sliceOfText))
copy(arrOfTextBytes[:], pseudoBits)
decryptedChunk := decryptByChunk(arrOfTextBytes, s.key)
decryptedBytes = append(decryptedBytes, decryptedChunk[:]...)
}
decryptedText := viewBytesAsBits(decryptedBytes)
return string(decryptedText), nil
}
func decryptByChunk(decryptedChunk [64]byte, key [64]byte) [64]byte {
startPermutatedChunk := startPermutation(decryptedChunk)
decryptedData := decryptByCycle(startPermutatedChunk, key)
return decryptedData
}
func decryptByCycle(bytesBlock [64]byte, key [64]byte) [64]byte {
var r [32]byte
var l [32]byte
var tmp [32]byte
copy(r[:], bytesBlock[0:32])
copy(l[:], bytesBlock[32:64])
for i := 15; i >= 0; i-- {
kIter := generate48BitKey(key, decryptShiftingPositions, i)
tmp = l
l = r
r = bytesXor(tmp, convertByFestel(r, kIter))
}
var decryptedBytes [64]byte
copy(decryptedBytes[:], append(l[:], r[:]...))
resBytes := lastPermutation(decryptedBytes)
return resBytes
}
Также тут можно посмотреть результат и более подробное описание алгоритма.
Запустить и потрогать можно тут.
P.s. Никоем образом не претендую на единтсвенное правильное решение, а также на хорошее знания языка Go, возможно что-то можно сделать лучше. Например неплохо было бы шифровать блоки в горутинах и ловить результат по каналам.