Задача
Рассматривая входной поток как последовательность бит, зашифруйте его при помощи восьмибитового самосинхронизирующегося скремблера. Начальное значение и обратные связи скремблера должны быть заданы в программе значениями двух переменных типа unsigned char. Как расшифровать полученный код.
Примечание: разобьём данную нам задачу на две подзадачи. В первой будет рассмотрено скремблирование входных данных, а во второй будет проведено дескремблирование исходных данных первой подзадачи.
Подзадача 1
Рассматривая входной поток как последовательность бит, зашифруйте его при помощи восьмибитового самосинхронизирующегося скремблера.
Входные данные
Некая символьная последовательность.
Выходные данные
Зашифрованная символьная последовательность.
Тесты
| Входные данные | Выходные данные |
|---|---|
| Dogs eat meat. | ea 27 33 77 25 11 66 75 5 3b e0 89 6b fa |
| Scramble it! | fc 5a 80 ef 75 43 1e 92 9b 46 57 6 |
| Base, base, it’s cheeseburger 1. Can you hear me? | ec 49 a0 c9 72 75 43 13 55 66 28 80 e7 ed d2 75 b7 bf 69 93 c7 df 4e d0 be 3f b1 de 5c f6 ea 6c 94 f5 8d 1f 86 80 aa 74 5e c7 9e 17 2 47 41 76 7c d4 a1 |
Код программы
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 |
#include<iostream> using namespace std; class self_synchronizing_scrambler { unsigned char key; unsigned char shift_register; bool pickbit(const unsigned char val, const short index) { return ((val >> index)%2); } public: self_synchronizing_scrambler() {} self_synchronizing_scrambler(unsigned char key, unsigned char shift_register) { this->key = key; this->shift_register = shift_register; } void assign_key(unsigned char key) {this->key = key;} void assign_register(unsigned char shift_register) {this->shift_register = shift_register;} unsigned char key_value() {return key;} unsigned char register_value() {return shift_register;} void scramble(unsigned char &letter) { unsigned char output = 0; for (unsigned char i = 0; i < 8; ++i) { bool newbit = pickbit(letter, 7-i); for (unsigned char j = 0; j < 8; ++j) { newbit ^= pickbit(this->key, 7-j) & pickbit(this->shift_register, 7-j); } output ^= (newbit << (7-i)); key = (key >> 1) + (newbit << 7); } letter = output; } void descramble(unsigned char &letter) { unsigned char output = 0; for(unsigned char i = 0; i < 8; ++i) { bool oldbit = pickbit(letter, 7-i), scrambit = 0; for(unsigned char j = 0; j < 8; ++j) { scrambit ^= pickbit(this->key, 7-j) & pickbit(this->shift_register, 7-j); } output ^= ((scrambit^oldbit) << (7-i)); key = (key >> 1) + (oldbit << 7); } letter = output; } }; int main() { self_synchronizing_scrambler A(5, 17); unsigned char input; while (scanf("%c", &input)) { if (input == '\n') break; A.scramble(input); printf("%x ", input); } return 0; } |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 |
import java.util.*; import java.io.*; class SelfSynchronizingScrambler { private char key, shift_register; private static int pickbit(char val, int index) { return ((val >> index)%2); } public SelfSynchronizingScrambler() {} public SelfSynchronizingScrambler(char key, char shift_register) { this.key = key; this.shift_register = shift_register; } public void assignKey(char key) {this.key = key;} public void assignRegister(char shift_register) {this.shift_register = shift_register;} public char keyValue() {return key;} public char registerValue() {return shift_register;} public char scramble(char letter) { char output = 0; for (char i = 0; i < 8; ++i) { int newbit = pickbit(letter, 7-i); for (char j = 0; j < 8; ++j) { newbit ^= pickbit(this.key, 7-j) & pickbit(this.shift_register, 7-j); } output ^= (newbit << (7-i)); key = (char)((key >> 1) + (newbit << 7)); } return output; } public char descramble(char letter) { char output = 0; for(char i = 0; i < 8; ++i) { int oldbit = pickbit(letter, 7-i), scrambit = 0; for(char j = 0; j < 8; ++j) { scrambit ^= pickbit(this.key, 7-j) & pickbit(this.shift_register, 7-j); } output ^= ((scrambit^oldbit) << (7-i)); key = (char)((key >> 1) + (oldbit << 7)); } return output; } }; public class Main { public static void main (String[] args) throws java.lang.Exception { SelfSynchronizingScrambler A = new SelfSynchronizingScrambler((char)5,(char)17); PrintWriter out = new PrintWriter(System.out); char letter = (char)System.in.read(); while(letter != '\n') { out.print((int)(A.scramble(letter))); out.print(' '); letter = (char)System.in.read(); } out.flush(); } } |
Решение задачи
Для зашифровки будем использовать стандартный алгоритм скремблирования. Скремблером будет переменная
key, которая изначально равна [latex]5[/latex]. Выбирать из скремблера будем нулевой и четвёртый биты. Входные данные будут поступать в переменную
input, после чего на них и на скремблере будет применяться функция
scram.
Так как входные данные имеют формат
unsigned char, считывание не прекратится никогда вплоть до принудительной остановки программы, ведь любые входные данные могут быть восприняты как символы. Для предотвращения этого, необходим символ, который будет служить «сигналом» для остановки программы. В нашем случае, это будет символ перехода на следующую строку.
Основная проблема задачи заключается в выводе зашифрованных данных, так как в результате скремблирования некоторые символы могут оказаться не отображаемыми. Дабы избежать подобной ситуации, зашифрованные данные будем выводить в шестнадцатеричном (для кода на Java — в десятичном) числовом формате.
Подзадача 2
Расшифровать входные данные из предыдущей подзадачи.
Входные данные
Некие зашифрованные данные, записанные в виде последовательности чисел шестнадцатеричного (для кода на Java — десятичного) формата.
Выходные данные
Расшифрованные данные.
Тесты
| Входные данные | Выходные данные |
|---|---|
| ea 27 33 77 25 11 66 75 5 3b e0 89 6b fa | Dogs eat meat. |
| fc 5a 80 ef 75 43 1e 92 9b 46 57 6 | Scramble it! |
| ec 49 a0 c9 72 75 43 13 55 66 28 80 e7 ed d2 75 b7 bf 69 93 c7 df 4e d0 be 3f b1 de 5c f6 ea 6c 94 f5 8d 1f 86 80 aa 74 5e c7 9e 17 2 47 41 76 7c d4 a1 | Base, base, it’s cheeseburger 1. Can you hear me? |
Код программы
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 |
#include <iostream> using namespace std; class self_synchronizing_scrambler { unsigned char key; unsigned char shift_register; bool pickbit(const unsigned char val, const short index) { return ((val >> index)%2); } public: self_synchronizing_scrambler() {} self_synchronizing_scrambler(unsigned char key, unsigned char shift_register) { this->key = key; this->shift_register = shift_register; } void assign_key(unsigned char key) {this->key = key;} void assign_register(unsigned char shift_register) {this->shift_register = shift_register;} unsigned char key_value() {return key;} unsigned char register_value() {return shift_register;} void scramble(unsigned char &letter) { unsigned char output = 0; for (unsigned char i = 0; i < 8; ++i) { bool newbit = pickbit(letter, 7-i); for (unsigned char j = 0; j < 8; ++j) { newbit ^= pickbit(this->key, 7-j) & pickbit(this->shift_register, 7-j); } output ^= (newbit << (7-i)); key = (key >> 1) + (newbit << 7); } letter = output; } void descramble(unsigned char &letter) { unsigned char output = 0; for(unsigned char i = 0; i < 8; ++i) { bool oldbit = pickbit(letter, 7-i), scrambit = 0; for(unsigned char j = 0; j < 8; ++j) { scrambit ^= pickbit(this->key, 7-j) & pickbit(this->shift_register, 7-j); } output ^= ((scrambit^oldbit) << (7-i)); key = (key >> 1) + (oldbit << 7); } letter = output; } }; int main() { self_synchronizing_scrambler A(5,17); unsigned short scrambled; unsigned char output; while (cin >> hex >> scrambled) { output = scrambled; A.descramble(output); cout << output; } return 0; } |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 |
import java.util.*; import java.io.*; class SelfSynchronizingScrambler { private char key, shift_register; private static int pickbit(char val, int index) { return ((val >> index)%2); } public SelfSynchronizingScrambler() {} public SelfSynchronizingScrambler(char key, char shift_register) { this.key = key; this.shift_register = shift_register; } public void assignKey(char key) {this.key = key;} public void assignRegister(char shift_register) {this.shift_register = shift_register;} public char keyValue() {return key;} public char registerValue() {return shift_register;} public char scramble(char letter) { char output = 0; for (char i = 0; i < 8; ++i) { int newbit = pickbit(letter, 7-i); for (char j = 0; j < 8; ++j) { newbit ^= pickbit(this.key, 7-j) & pickbit(this.shift_register, 7-j); } output ^= (newbit << (7-i)); key = (char)((key >> 1) + (newbit << 7)); } return output; } public char descramble(char letter) { char output = 0; for(char i = 0; i < 8; ++i) { int oldbit = pickbit(letter, 7-i), scrambit = 0; for(char j = 0; j < 8; ++j) { scrambit ^= pickbit(this.key, 7-j) & pickbit(this.shift_register, 7-j); } output ^= ((scrambit^oldbit) << (7-i)); key = (char)((key >> 1) + (oldbit << 7)); } return output; } }; public class Main { public static void main (String[] args) throws java.lang.Exception { Scanner in = new Scanner(System.in); PrintWriter out = new PrintWriter(System.out); SelfSynchronizingScrambler A = new SelfSynchronizingScrambler((char)5,(char)17); char scrambled; while(in.hasNextInt()) { scrambled = (char)in.nextInt(); out.print(A.descramble(scrambled)); } out.flush(); } } |
Решение задачи
Для расшифровки будем применять обратный алгоритм к использованному в предыдущей задаче. Значение необходимого для расшифровки дескремблера нам известно из предыдущей задачи (а именно — [latex]5[/latex]), поэтому его мы и используем.
Входные данные будут считываться методом
cin (для C++), где параметр
hex будет указывать на то, что данные поданы в шестнадцатеричном формате. После считывания на входных данных будет применяться алгоритм дескремблирования, и итоговые данные будут выведены на экран.
Ссылки
- Оригинал скремблера (C++);
- Оригинал дескремблера (C++);
- Оригинал скремблера (Java);
- Оригинал дескремблера (Java);
- Условие задачи.