14 Окт


2018

Реализация алгоритма шифрования DES.

Меня всегда занимала криптография, задолго до того как я стал интересоваться программированием. Это своего рода проявление свободы в сети. Я тверждо убежден что никто ни под какими предлогами не имеет право на доступ к вашим данным, это путь мрака и тоталитаризма. 

Вместе с тем я всегда думал что криптография для меня сложна и недостежима (разумеется рот13 в расчет не идет, тут все тривиально). Однако DES оказался достаточно простым в понимании (и чуть более сложным в реализации, но это уже моя оплошность). Шифрование является симметричным, т.е. ключ который шифрует данные их же и расшифровывает. 

Моя имплементация алгоритма была реализована на языке Go, на основе описания с викпедии. Она не является лучшей, и даже хорошей. Но об этом чуть ниже.

Итак, первый пункт википедии описывает уже саму схему алгоритма, я использовал шифрование текста. Поэтому перед тем как начать писать сам код я использовал небольшой конструктор, который делал ровно  следующее:

  1. Приводим текст к размерности кратной 64 байта. (Можно дополнить просто 0, для шифрования текста я дополнял пробелами в конце, возможно это снижает криптоустойчивость, однако функцию расширения достаточно просто изменить, к тому же алгоритм лишь для обучения, оставляю так)
  2. Преобразуем ключ 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, возможно что-то можно сделать лучше. Например неплохо было бы шифровать блоки в горутинах и ловить результат по каналам.

криптография