Шифр Виженера

Harvard CS50

2 уровень , 9 лекция

Открыта

Теория

Шифр Виженера несколько безопаснее шифра Цезаря: в качестве ключа в нем используется слово и его сложно взломать вручную с помощью одного только частотного анализа или перебора. Каждая буква ключа генерирует число, и в результате мы получаем несколько ключей для сдвига букв.

Пример:

p = Meet me in the park at eleven am 
В качестве ключевого слова возьмем 
k = bacon
Длина сообщения p = 25 
В то время как длина k = 5 
Поэтому его нужно повторять 5 раз.

Если число букв в сообщении не делится на ключ нацело, мы в последнем применении ключа используем только его часть:

Чтобы найти значение для смещения, используем позиции каждой буквы нашего ключа bacon в алфавите (от a до z). Считаем с нуля, как истинные программисты. И каждую букву в оригинальном тексте смещаем на заданное число, как в шифре Цезаря, возвращаясь при надобности после Z в начало алфавита. Таким образом, M сместится на 1, первая e вообще не сместится, а вторая сместится на 2 позиции. Ниже вы видите изначальное сообщение, расписанный ключ и результат его применения.

Шифр Виженера, конечно, понадежнее, но если вы знаете длину ключа, его сломать довольно просто. Как её выявить? Если оригинальный текст достаточно длинный, чтобы некоторые слова встречались в нем несколько раз, то вы увидите некоторые повторения:

Также можно использовать полный перебор, но вариантов немало: 26^n – 1 где n — длина неизвестного ключа. Но обычно это немало. Правда, для компьютера это не проблема.

А теперь математика шифра:

Пусть р – некоторый текст, k — ключевое слово, kj— j-я буква ключа, pi — буква под номером i в оригинальном тексте, ci — буква под номером i в шифровке. Тогда:

ci = (pi + kj) % 26

Предыдущая Предыдущая лекция

Следующая Следующая лекция

Комментарии (10)

ЧТОБЫ ПОСМОТРЕТЬ ВСЕ КОММЕНТАРИИ ИЛИ ОСТАВИТЬ КОММЕНТАРИЙ,
ПЕРЕЙДИТЕ В ПОЛНУЮ ВЕРСИЮ

Kateryna Piskovets Уровень 1

5 декабря 2020

почему выдает ошибку asd.c:53:40: error: use of undeclared identifier 'k' int ci=(char)(p[i]+key[k]-65)%26+65; #include <stdio.h> #include <cs50.h> #include <string.h> #include <stdlib.h> #include <ctype.h> int main(int argc, string argv[]) { if (argc != 2 ) { printf("chto-to nie to/n"); return 1; } else //исключаем возможность ввода аргумента типа baco1/113 { for (int j=0;j<strlen(argv[1]); j++ ) { if (!isalpha(argv[1][j])) { printf("Incorrect argument\n"); return 1; } } } string p = get_string("twoj tekst\n"); string key = argv[1]; int steps[strlen(key)]; { for(int k=0; k<strlen(key); k++) { if (islower(key[k])) { steps[k] = (char)(key[k]-97); } else { steps[k] = (char)(key[k]-65); } } int j = 0; for(int i=0; i<strlen(p); i++) { { if (isalpha(p[i])) { if (isupper(p[i])) { int ci=(char)(p[i]+key[k]-65)%26+65; printf("%c", ci); } else { int di=(char)(p[i]+key[k]-97)%26+97; printf("%c", di); } } } if(j>=strlen(key)) { j=0; } else { printf("%c", p[i]); } printf("\n"); return 0; } } }

Инна Ромашко Уровень 0

25 октября 2020

#include<stdio.h> #include<cs50.h> #include<string.h> #include <ctype.h> int main(int argc, string argv[]) { //проверяем количество аргументов if (argc != 2) { printf("Invalid number of arguments\n"); return 1; } //исключаем возможность ввода аргумента типа baco1/113 else { for (int j=0, m=strlen(argv[1]); j<m; j++) { //если встречаем не алфавитную букву if (!isalpha(argv[1][j])) { printf("Incorrect argument\n"); return 1; } } } //запрашиваем текст string p = get_string("Enter your text\n"); //объявляем переменную ключа string key = argv[1]; //создаем массив длиной в ключ //в нем будет храниться длина шагов int steps [strlen(key)]; for (int k=0, kl=strlen(key); k<kl; k++) { //если символ ключа строчный if (islower(key[k])) { steps[k] = (char)(key[k]-97); } //если символ прописной else { steps[k] = (char)(key[k]-65); } } int j = 0; //приступаем к шифрованию текста for (int i=0, n=strlen(p); i<n; i++) { if (isalpha(p[i])) { if (islower(p[i])) { int ci = (char)(p[i]-97 + steps[j])%26+97; printf ("%c", ci); } else { int ci=(char)(p[i]-65 + steps[j])%26+65; printf("%c", ci); } //счетчик символов массива ключа увеличивается на 1 //каждый раз после использования j++; //если счетчик равен длине ключа, он обнуляется и нарастает заново if (j>=strlen(key)) { j=0; } } //иначе просто выводим символ else { printf ("%c", p[i]); } } printf("\n"); return 0; }

xacker Уровень 5

14 июня 2020

Вариант без cs50.h и ctype.h


//Viginere code
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int key_to_num (int key)
{
	if ((key >= 'A') && (key <= 'Z')) 
		{
			key = key - 'A';
		}
	else if ((key >= 'a') && (key <= 'z')) 
		{
			key = key - 'a';
		}
	return key;
}

int main(int argc, char* argv[])
{
	if(argc < 2)
	{
		fprintf(stderr, "Not enough arguments\n");
		return 1;
	}
	if(argc > 2)
	{
		fprintf(stderr, "Too many arguments\n");
		return 1;
	}

	int key[101] = {0};
	int key_max = 0;

	for (int i = 0, n = strlen(argv[1]); i < n; ++i)
	{
		key[i] = key_to_num(argv[1][i]);
		if (i == n - 1) key_max = i + 1;
	}

	char str[101] = {'0'};
	printf("Enter string for cipher: ");
	fgets(str, 100, stdin);

	for (int i = 0, j = 0, n = strlen(str); i < n; ++i)
	{
		if ((str[i] >= 'A') && (str[i] <= 'Z')) 
		{
			str[i] = 'A' + ((str[i] - 'A' + key[j % key_max]) % 26);
			j++;
		}
		else if ((str[i] >= 'a') && (str[i] <= 'z'))
		{
			str[i] = 'a' + ((str[i] - 'a' + key[j % key_max]) % 26);
			j++;
		}

	}
	printf("Cipher string is: %s\n", str);
}

Алексей Уровень 31

3 мая 2020

ГОТОВО за 2 часа спилил, из палок, не стал упрощать, сделал как можно больше простого кода, если кто решит доработать, буду рад увидеть более простую и понятную новичку код) вроде протестил, все работает))) Код на диске, тк JavaRush не позволяет большое количество символов в комментах

дима тарасов Уровень 4

24 октября 2019

Скопипастил, пишите сами это чисто для проверки как работает.


#include <stdio.h>
#include <string.h>
#include <cs50.h>
#include <ctype.h>
#include <stdlib.h>

// Global variables
string crypto_key;
int length_key = 0;
int alpha_text_count = 0;
int k = 0;
// Function declaration
bool is_aplha_string(string str);
void set_k_value(void);
int get_encrypt_char(char decrypt_char);

int main(int argc, string argv[])
{
    // Check if have argument key and is it only aplha chars
    if (argc != 2 || !is_aplha_string(argv[1]))
    {
        printf("Usage: ./vigenere k\n");
        return 1;
    }
    crypto_key = argv[1];
    length_key = strlen(crypto_key);
    // Get text to encrypt
    printf("plaintext: ");
    string text = get_string("Вводи слово");
    int lenght_text = strlen(text);
    printf("ciphertext: ");
    // Loop for encrypt one char in text
    for (int i = 0; i < lenght_text; i++)
    {
        printf("%c", get_encrypt_char(text[i]));
    }
    printf("\n");
    return 0;
}

// Function check is string have only aplha chars
bool is_aplha_string(string str)
{
    int len = strlen(str);
    for (int i = 0; i < len; i++)
    {
        if (!isalpha(str[i]))
        {
            return false;
        }
    }
    return true;
}

// Function set k value by current alpha char in text
void set_k_value(void)
{
    int i = alpha_text_count % length_key;
    int ascii_start_number = isupper(crypto_key[i]) ? 65 : 97;
    k = (crypto_key[i] % ascii_start_number) % 26;
    alpha_text_count++;
}

// Function encrypt char via number ASCII code
int get_encrypt_char(char decrypt_char)
{
    if (isalpha(decrypt_char))
    {
        set_k_value();
        int ascii_start_number = isupper(decrypt_char) ? 65 : 97;
        return (((decrypt_char % ascii_start_number) + k) % 26) + ascii_start_number;
    }
    else
    {
        return decrypt_char;
    }
}

kovalevcon Уровень 11

26 июля 2018

Мои решения с описанием команд для каждого задания: Github CS50

Arhi Demon Уровень 0

28 апреля 2018

Проще не куда, некотырые изменения предыдущей задачи и вуаля

Alexandr Grigoryev Уровень 17

26 апреля 2018

Походу ни кто так и не сделал) Попробуем)