• ,

Гарвард CS50: задания второй недели (лекции 5 и 6)

cs50 задания к лекциям 5 и 6

Лекции CS50 лежат здесь: http://javarush.ru/cs50.html. В этом материале — 3 задания, теоретические сведения к ним и руководство к действию.

Цели


• Углубиться в функции и библиотеки
• Познакомиться с криптографией, реализовать пару простых шифров

Дополнительные материалы


reference.cs50.net/ — разъяснение функций библиотек, используемых во время обучения. На английском.
http://computer.howstuffworks.com/c.htm стр. 11 – 14 и 39

Подготовка


Залогиньтесь на cs50.io, выполните

update50

чтобы убедиться в актуальности версии вашего рабочего пространства. Если вы случайно закрыли терминальное окно, зайдите в меню View и убедитесь, что напротив пункта Console стоит галочка (поставьте её, если это не так).


Кликните на(+), внутри зеленого круга на рамке терминального окна, выберите New Terminal.


Создайте рабочую директорию:

mkdir ~/workspace/pset2

Обратите внимание: между mkdir и ~/workspace/pset2 есть пробел. Напомним, ~ означает корневой каталог, ~/workspace — папка, называемая рабочим пространством, находится внутри корневого каталога, ~/workspace/pset2 — директория по имени pset2 внутри ~/workspace.
Теперь выполните:

cd ~/workspace/pset2

чтобы перейти в новую директорию.

Командная строка выглядит примерно так:

username:~/workspace/pset2 $

Если что-то не так, повторите шаги. Также можете вызвать команду

history

чтобы просмотреть последние несколько команд в хронологическом порядке. Также вы можете, установив курсор на командную строку и нажимая стрелку «вверх» на клавиатуре, просматривать все команды в порядке от последней введенной к первой. С помощью кнопки «вниз» вы можете идти обратно. Кстати, вместо того, чтобы каждый раз набирать одни и те же команды, вы можете прокручивать уже набранные команды и выполнять их снова, нажимая на Enter. Вы могли заметить, что Дэвид на лекциях делает именно так.

Задачи второй недели нужно сохранять в pset2.

Задание 0. Инициализация


Ознакомимся со строками поближе. В файле initials.c напишите программу, которая запрашивает имя пользователя (с помощью функции GetString получаем имя в виде строки) и затем выводит первые буквы имени (или имен) и фамилии в верхнем регистре без пробелов, точек и прочих знаков, только с переводом строки (\n). Предполагаем, что пользователи вводят исключительно буквы (в нижнем или верхнем регистре, или обоих сразу) плюс по одному пробелу между словами. Считайте, что ребята с именами Joseph Gordon-Levitt, Conan O’Brien или David J. Malan не будут пользоваться программой.

username:~/workspace/pset2 $ ./initials
<u>Zamyla Chan</u>
ZC
username:~/workspace/pset2 $ ./initials
robert thomas bowden
RTB

Для проверки корректности работы программы вызывайте check50:

check50 2015.fall.pset2.initials initials.c

Хотите поиграться с реализацией программы, подготовленной сотрудниками CS50? Набирайте строку:

~cs50/pset2/initials


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

Криптография, наука о шифровке и дешифровке информации… На самом деле зашифрованные послания существуют с древних времён, и использовались армиями для передачи секретных сообщений. Ну и сейчас ваши пароли в Facebook и других сетях хранятся в зашифрованном виде.

Задание 1. Аве, Цезарь!


Теоретические сведения
Мы изучим один из простейших шифров — шифр Цезаря, названный в честь римского императора. В этом шифре каждая буква текста заменяется на другую, которая находится на фиксированное число букв ниже в алфавите. Это фиксированное число букв называется ключом. Так, ключ 1 переводит букву латиницы C в букву D, а Z — по циклу в A. Если ключ 3, то буква C перейдет в F, а Z — в C.

Примеры: используем шифр Цезаря с ключом 5 на слове cat.

c -> h
a -> f
t -> y 
Caesar (cat, 5) = hfy

Ключ = 7, слово = computer

c->j
o->v
m->t
p->w
u->b
t->a
e->l
r->y
Caesar(computer,7) = jvtwbaly



Шифр Цезаря прост, но, увы, ненадёжен (это взаимосвязанные вещи!): для английского алфавита — всего 25 вариантов шифровки, перебрать все варианты легко даже без компьютера. Тем не менее, шифр Цезаря часто используют в качестве шага в других шифрах, таких, как шифр Виженера (о нём — в следующем пункте).

«Математизируем» шифр Цезаря. Обозначим незашифрованный текст буквой p, pi — буква в тексте p, которая находится на позиции с номером i. Назовем секретный ключ буквой k, с — зашифрованный текст, а ci — буква в шифрованном тексте, которая находится на позиции i. Тогда вычислить каждую букву шифра можно по формуле:

ci = (pi + k) % 26

Привыкайте к такой формализации, она позволяет программировать алгоритм и выражает смысл шифра точно и сжато.
Если ключ k = 13 а изначальный текст p — «Be sure to drink your Ovaltine!», вот какой шифр мы получим:

Or fher gb qevax lbhe Binygvar!


Обратите внимание, O (первая буква в шифрованном тексте) смещена на 13 позиций от буквы B (первая буква в оригинальном тексте). То же самое с буквой r (вторая буква в шифровке) смещена на 13 букв от e (вторая буква в оригинале). Третья буква в шифровке, f, смещена на 13 букв от s (третья в оригинале), тут мы ходим по кругу от z до a.

Шифр Цезаря с ключом 13 имеет специальное название ROT13. Он симметричный: применив его дважды, мы вернемся к изначальному тексту. Конечно, есть еще и ROT26, этот вообще супер-секьюрный, но только если вы нечетко выражаете свои мысли=).

Условие

Написать в файле caesar.c, программу, шифрующую текст с помощью шифра Цезаря. На вход программы подавайте один аргумент командной строки: не негативное целое число. Для простоты назовем его k. Если пользователь выполняет программу без аргументов командной строки или более, чем с одним аргументом, приложение должно возмутиться и вернуть значение 1 (обычно так обозначают ошибки):
return 1;

Во всех других случаях программа запрашивает у пользователя текст, который нужно зашифровать, затем выводит на экран текст, зашифрованный ключом k (т.е., смещенный на k позиций вправо по циклу). Если в тексте есть символы, выходящие за пределы английского алфавита, их программа не меняет. После вывода шифрованного текста, приложение завершает работу,main возвращает 0:

return 0;

Если main не возвращает нуль явно, он возвращается автоматически (на самом деле int — тип, возвращаемый main, но об этом в другой раз). Согласно конвенции (правилам хорошего тона в программировании), если вы явно возвращаете 1 чтобы указать на ошибку, то нужно вернуть и 0 в качестве указателя на успешное завершение работы программы.

Хотя в английском алфавите только 26 букв, k может быть и больше 26. По сути, ключ k = 27 даст тот же результат, что и k = 1, но нужно позволить пользователю вводить любое неотрицательное число, не превышающее 2^31 – 26 (оно должно поместиться в int). Программа также должна учитывать, что строчные буквы шифруются строчными, а прописные — прописными.

С чего начинаем? Поскольку приложение должно принять значение k непосредственно в строке аргументов, заголовок функции main у нас имеет следующий вид:

int main(int argc, string argv[])

Из шестой лекции вы знаете, что argv — это массив строк. Массив можно представить, как ряд шкафчиков-ячеек в спортзале. В каждом из них спрятано некоторое значение. В нашем случае, внутри каждой ячейки лежит аргумент типа

string

Чтобы открыть первый шкафчик, используем argv[0], второй — argv[1] и так далее. Если у нас есть n замков, то нам нужно остановиться на argv[n — 1], поскольку argv[n] уже не существует (или существует, но принадлежит кому-то ещё, нам лучше его не трогать).

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

string k = argv[1];

Мы полагаем, что там действительно что-то есть! Напомним, argc — переменная типа int, равная количеству строк argv. Значит, лучше проверить значение argc прежде, чем пытаться открыть ячейку, ведь может статься, что её не существует.

В идеале argc = 2. Почему так? Внутри argv[0] обычно находится имя программы. То есть, argc всегда не меньше 1. Но нашей программе нужно, чтобы пользователь предоставил аргумент командной строки k, следовательно, argc = 2. Естественно, если пользователь в командной строке введет более одного аргумента, argc также подрастает и может быть больше, чем 2.

Если пользователь вводит целое число в строку, это еще не значит, что внесенное значение будет автоматически сохранено в тип int. Точнее, оно НЕ будет. Оно будет string, даже если выглядит точь-в-точь, как int! Так что нам нужно конвертировать string в int самостоятельно. К счастью, существует функция atoi, созданная для этих целей. Её синтаксис:

int k = atoi(argv[1]);

Обратите внимание: k имеет тип int, поэтому с ним можно провернуть арифметические действия. С этой функцией не нужно беспокоиться, введет ли пользователь целое число, или, скажем, foo: в таком случае atoi возвратит 0.

Функция atoi объявлена в библиотеке stdlib.h, поэтому не забудьте прописать её директивой #include в начале программы. Код и без этого скомпиллируется, поскольку мы уже включили эту функцию в библиотеку cs50.h. Тем не менее, лучше доверять нативным библиотекам.

Итак, вы получили k, сохраненное как int. Теперь запросим ввод текста. Если вы делали задания первой недели, то уже знакомы с функцией библиотеки CS50, которая называется GetString. Она-то нам и поможет.

После того, как вы получили k и начальный текст, приступим к шифрованию. Напомним, вы можете пройтись по всем символам строки и напечатать их с помощью следующего цикла:

for (int i = 0, n = strlen(p); i < n; i++)
{
    printf("%c", p[i]);
}

Другими словами, точно так же, как argv — массив строк, string является массивом символов. Поэтому мы можем использовать квадратные скобки для доступа к отдельным элементам строки точно так же, как получать отдельные строки в argv. Конечно, нет ничего криптографического в печати каждого из символов. Или, технически, когда k = 0. Но мы же должны помочь Цезарю зашифровать его текст! Аве, Цезарь!

Чтобы использовать strlen, нужно подключить ещё одну библиотеку.

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

username:~/workspace/pset2 $ ./caesar 13
Be sure to drink your Ovaltine!
Or fher gb qevax lbhe Binygvar!


Помимо atoi, вы можете найти другие классные функции в библиотеках ctype.h и stdlib.h. Для этого перейдите по ссылке и поройтесь там немного. Например, isdigit — явно что-то интересное=).
Когда переходите от Z к A (или от z к a), не забывайте об операторе деления по модулю % в языке С. Также изучите таблицу, она показывает символы ASCII не только для букв.

Чтобы проверить правильность работы программы с check50, выполните следующее:

check50 2015.fall.pset2.caesar caesar.c

А если вам интересно поиграть с кодом, сделанным сотрудниками СS50, выполните команду:

~cs50/pset2/caesar


Кстати, uggc://jjj.lbhghor.pbz/jngpu?i=bUt5FWLEUN0.

Разбор задания
  1. Получить ключ
  2. Получить текст
  3. Зашифровать
  4. Вывести на экран зашифрованное сообщение

1. Формируем функцию main так, чтобы пользователь вводил ключ в командной строке и проверяем ключ на корректность.

int main(int argc, string argv[])

argc:
• int
• количество аргументов, введенных в командную строку
• если argc = 2 все ок. Если нет, выводим инструкцию и закрываем программу.
• Если argc = 2 проверяем, является ли ключ целочисленным
• Argv — это массив строк, список с введенными в него аргументами

Массив — структура данных, содержащая разные данные одного типа в разных ячейках.


Например, пользователь ввел строку blastoff Team Rocket, тогда:


Переводим с помощью функции atoi() полученное в целое число. Если это невозможно, функция вернет 0.



2. Запрос у пользователя текста. Это просто: всё, что вводит пользователь, является строкой.
3. Шифрование. Алгоритм прост, но как пояснить компьютеру, какие буквы идут одна за другой? Самое время вспомнить о таблице ASCII!


Однако в строке могут быть не только буквы… Прежде, чем перейти к изменению строк, представьте, что нужно поменять только один символ. Мы хотим сменить буквы из начального текста, а не знаки или цифры. Что мы должны сделать? Для начала нам нужно проверить, есть ли этот символ в алфавите. Это можно сделать с помощью функции isalpha().

Если символ входит в алфавит, эта функция возвращает значение true и false во всех других случаях. Еще две полезные функции — isupper () и islower() возвращают true в случае, если буква прописная или строчная соответственно. Таким образом:

Isalpha(‘Z’) -> true
Isalpha(‘;’) -> false
Isupper(‘Z’) ->true
Isupper(‘z’) -> false
Islower(‘Z’) -> false
Islower(‘z’)->true


Если isalpha возвращает true, нам нужно поменять этот символ с помощью ключа.
Рассмотрим и разберем в качестве примера программу Замили, ассистента CS50.

/*
 * asciimath.c
 * by Zamyla Chan
 *
 * Calculates the addition of a char and an integer,
 * and displays both the resultant character and its
 * ASCII value.
 *
 * Usage: ./asciimath key [char]
 *
 */

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

int main(int argc, string argv[])
{

    if (argc != 2)
    	
    	{
 printf("print the key next time \n"); 
        return 1;
    	}
    // key is the second command line argument 

  
    int key = atoi(argv[1]); //преобразование строки в int 

    int letter = 'A';
    
    printf("\nCalculating '%c' + %d...\n", letter, key);
    
    int result = (letter + key);
        
    printf("The ASCII value of %c is %d.\n\n", result, result);
   
    return 0;
    

}

Вас может удивить, почему ‘A’ — это целое число, тогда как она явно является буквой. Оказывается символы и целые числа — взаимозаменяемы. Поставив букву A в одиночные кавычки можно получить её ASCII-код в int. Будьте внимательны: вам нужны именно одинарные кавычки, без них компилятор будет искать переменную по имени A, а не символ.

Затем в строке

int result = (letter + key);


мы прибавляем значение ключа к ASCII-коду буквы и сохраняем их в переменной целого типа. Даже если результат имеет тип int, оператор printf использует плейсхолдер %с для символов. Таким образом, программа печатает символ, связанный с целочисленным результатом. Во втором случае мы выводим на экран число с помощью плейсхолдера %d.

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



А теперь пусть ключ будет 26:



Мы получили [, а вовсе не букву A. Это просто следующий символ ASCII после Z. Так что простое прибавление ключа работать не будет. Нам нужно использовать формулу шифра, чтобы возвращаться в начало алфавита как только буквы закончатся.
Помните, мы уже писали выше:

ci = (pi + k) % 26

Где ci — буква номер i в шифрованном тексте, pi — буква номер i в незашифрованном тексте, k — ключ, а %26 — остаток от деления на 26 (или «деление по модулю 26»).

Давайте применим эту формулу для буквы Y. Возьмем k = 2. Посчитаем (‘Y’ + 2) %26
ASCII-код буквы ‘Y’= 89. Тогда
(‘Y’ + 2) %26 = (89 + 2)%26 = 91%26 = 13

Но это вовсе не ASCII-значение нужной нам буквы A, которое равно 65.

Теперь давайте придадим каждой букве алфавита значение от 0 до 25 по порядку. В таком случае Y = 24.
(24+2)%26 = 0
Буква А как раз имеет такой индекс. Таким образом, эта формула относится к алфавитному индексу букв, а не их ASCII-значений.

Для печати зашифрованного символа вам нужно будет его ASCII-значение. И разберитесь с тем, как переключаться между ASCII-значением и номером в алфавите.
После того, как мы выяснили формулу для одного символа, нужно применить её для каждой буквы во вводимой с клавиатуры строке. Но только если это буквы!
И помните, для больших и малых букв нужны разные значения. Тут пригодятся функции isupper и islower. У вас может быть две формулы, одна для больших букв, другая — для малых, функции помогут выбрать, какую из них применить.

Как применить формулу к каждому отдельному символу в строке? Помним, что строка — это просто массив символов. Определить количество итераций в цикле поможет функция strlen (длина строки).


Задание 2. Parlez-vous français?

Теория

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

Пример:

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

Задание
Условие

Написать программу vigenere.c, которая шифрует сообщение с помощью шифра Виженера. На вход программы подаем один аргумент командной строки: ключевое слово k, состоящее из букв английского алфавита. Если приложение запускается более чем с одним аргументом или с аргументом не входящим в алфавит, нужно вывести информацию об ошибке с завершением программы. То есть main будет возвращать 1 — в таком случае наши автоматические тесты поймут, что здесь все хорошо, и это условие учтено. Если всё хорошо, программа должна перейти к запросу строки текста p, который мы и шифруем полученным выше ключом k, напечатать результат и завершить выполнение программы, возвратив значение 0.
Уточнение

Нужно сделать так, чтобы в ключе k символы A и a обозначались как 0, B и b как 1, ..., Z и z как 25. Программа должна применять шифр Виженера только к буквам текста p. Остальные символы (цифры, знаки препинания, пробелы) нужно вывести без изменений. Если алгоритм собирается применить j-й символ k к i-му символу p, не входящему в алфавит, применяем этот j-й символ ключа к следующему алфавитному символу в тексте; вы не можете просто оставить его и перейти к другому символу в k. Наконец, программа должна сохранить регистр каждой буквы в p.

Не знаете, с чего начать?




Вот вам несколько советов от Замили, ассистента курса CS50

К счастью, программа очень похожа на шифр Цезаря, только в качестве ключа используется не целое число, а строка. Если вы успешно реализовали шифр имени римского правителя, он может стать прекрасным стартом для реализации второго задания. Вы, вероятно, уже смекнули, что шифр Виженера с одной буквой в качестве ключа — это тот же шифр Цезаря.
В алгоритме Виженера применяются те же шаги, что и в «Цезаре»:
  1. Получить ключ
    • кодовое слово — это второй аргумент командной строки argv[1]
    • должен входить в алфавит: функция isalpha

  2. Получить текст
  3. Зашифровать
  4. Напечатать шифрованный текст
Итак, второй аргумент командной строки argv[1] проверим на принадлежность к алфавитным символам. Делаем это с помощью уже знакомой isalpha. Если ключ корректен, получаем от пользователя строку и начинаем шифровать.

Формула шифра Виженера похожа на формулу шифра Цезаря. Каким образом вы преобразуете букву на соответствующее смещение шифра? Попробуйте сравнить значения по таблице ASCII.


Скорее всего, у вас получится отыскать закономерность между буквами и их алфавитными индексами используя последовательности в таблице. Догадались, как отнять одну букву от другой, чтобы получить желаемый результат? Смещения для больших и малых букв одинаковы, так что вам придется определить две похожие формулы для определения смещения для строчных и отдельно для прописных букв.
Также не забудьте, что цикл прохода по тексту должен игнорировать символы, не входящие в английский алфавит. И не забудьте сохранить регистр букв.
Если посмотреть на формулу шифра:

ci = (pi + kj) % 26

вы увидите две индексные переменные, i и j. Одна сохраняет позицию в исходном тексте, другая — в ключе. Если ваш текст длиннее ключа, индекс по ключу проходит с конца ключа снова в его начало.
Как это сделать? С помощью операции деления по модулю! Результат операции — остаток от деления двух чисел. Практическая польза этой операции в программировании просто огромна!

Представьте, что многочисленную группу людей нужно разделить на три подгруппы. Один из способов это сделать — попросить их рассчитаться на первый-второй-третий.


То есть, первый человек относится к первой группе, второй — ко второй, третий — к третьей, четвертый — снова к первой и так далее. Вы можете использовать деление по модулю чтобы произвести эту же операцию. Пронумеруем те же три группы с нуля. Вот как это делается:



Если вы возьмете индекс и поделите его по модулю максимального значения, полученный результат никогда не будет больше или равен этому значению.

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

Так как мы автоматизируем некоторые тесты вашего кода, программа должна вести себя так, как показано ниже:

jharvard@appliance (~/Dropbox/pset2): ./vigenere bacon
Meet me at the park at eleven am
Negh zf av huf pcfx bt gzrwep oz


Как еще можно протестировать программу, кроме ручного вычисления зашифрованного текста? Мы добрые: для этого мы написали программу devigenere. Она принимает один и только один аргумент командной строки (ключевое слово), а её работа заключается в том, чтобы принять зашифрованный текст в качестве входных данных и вернуть обычный.
Запустите её:

~cs50/pset2/devigenere k

Где k — ключевое слово.
Если вы хотите проверить правильность вашей программы с помощью check50, выполните:

check50 2014.fall.pset2.vigenere vigenere.c


А если хотите оценить нашу реализацию vigenere, наберите:

~cs50/pset2/vigenere


Как подтвердить правильность кода и получить оценки


Внимание! Если вам важно проверить только правильность задач, после того, воспользуйтесь cs50check. Если же вы ходите получить оценки на платформе edx, проделайте процедуру, описанную ниже. Имейте в виду, эта процедура для проверки задач использует ту же cs50check. Разница только в том, что она запоминает результаты и подсчитывает общую оценку.
  1. Залогиньтесь в CS50 IDE
  2. Рядом с левым верхним углом CS50 IDE, там, где расположен её файловый браузер (не в терминальном окне), кликните правой клавишей мыши по вашему файлу initials.c, находящемуся в директории pset2 и нажмите Download. Вы должны увидеть, что браузер загрузил initials.c.
  3. Повторите для caesar.c.
  4. Повторите для vigenere.c.
  5. В отдельном окне или вкладке залогиньтесь в CS50 Submit
  6. Кликните по иконке Submit в левом верхнем углу экрана.



  7. В списке папок слева кликните по директории Problem Set 2, затем нажмите на кнопку Upload New Submission. Она находится справа.



  8. На появившемся экране кликните по кнопке Add files…. Откроется окно выбора файлов с вашего компьютера.



  9. Перейдите к той папке, где вы храните initials.c. Скорее всего, он находится в папке Downloads («Загрузки») или там, куда ваш браузер складывает файлы по умолчанию. Когда найдете initials.c, кликните по нему один раз чтобы выбрать, затем кликните Open («Открыть»).
  10. Кликните Add files ещё разок.
  11. Найдите caesar.c и откройте его.
  12. Проделайте то же самое для файла vigenere.c.
  13. Нажмите Start upload. Ваши файлы будут загружены на серверы CS50.
  14. На появившемся экране вы должны увидеть окно No File Selected. Если вы переведете курсор мыши влево, вы увидите список загрузившихся файлов. Для подтверждения кликните по каждому из них. Если вы в чём-то не уверены, вы можете перезагрузить файлы, повторив те ж шаги. Вы это можете делать сколько угодно раз до конца 2016 года.

10 комментариев

NikSue
  • NikSue
  • 0
  • Комментарий отредактирован 2016-09-01 06:13:36 пользователем NikSue
Во втором задании в тексте описка, написано beacon вместо bacon, как на картинке
Masha
спасибо, исправили!
NikSue
Не хочу показаться занудным. Но вот ещё в одной строке забыли исправить:
«Чтобы найти значение для смещения, используем позиции каждой буквы нашего ключа beacon в алфавите (от a до z)».
sibkedr
пока не по теме задач, а по лекции вопрос
почему в этом коде
for (int i = 0; i < argc; i++)
    {
        for (int j = 0, n = strlen(argv[i]); j < n; j++)
        {
            printf("%c\n", argv[i][j]);
        }
        printf("\n");
    }

все введенные аргументы (а аргументы вводятся через пробел), печатаются с новой строки посимвольно в том числе и пробел тоже.
вот так
.
/
Z
m
a
l
y

N
a
m
e

а в этом
for (int i = 0; i < argc; i++)
    {
        for (int j = 0, n = strlen(argv[i]); j < n; j++)
        {
            printf("%c\n", argv[i][j]);
        }
        
    }

пробелы не печатаются
вот так. Я знаю, что это из-за того что в 1-м цикле внизу убрали printf("\n") — но не могу понять как работает
.
/
Z
m
a
l
y
N
a
m
e
sibkedr
Разобрался сам))
sibkedr
Подскажите, пожалуйста еще.
Какая книга имеется ввиду к этой теме (указана на сайте cdn.cs50.net/2015/fall/psets/2/pset2/pset2.html)
Chapters 7, 8, and 10 of Programming in C
NotSure
Говорят что такая: Stephen G. Kochan, «Programming in C», 3rd Edition
Можно найти в pdf
sibkedr
кто нибудь брался за взлом паролей из хакерского задачника 3-й недели? cdn.cs50.net/2015/fall/psets/2/hacker2/hacker2..
Не хватает знаний английского, чтобы до конца понять подсказки. Как я понял, нужно прочитать как работает функция, которая зашифровала эти пароли, для этого набрать команду в консоль man crypt
А вот что они дальше пишут где _XOPEN_SOURCE, где want to link with -lcrypt, и как почитать этот файл — You might also want to read up on C’s support for file I/O, as there’s quite a number of English words in /usr/share/dict/words
Общее представление понятно перевода, но боюсь что-то упустил. Пойду читать crypt и подтягивать английский.

As for their ciphertexts, you’d best pull up the «man page» (i.e., manual) for «crypt» by executing

man crypt
in a terminal window so that you know how the function works. In particular, make sure you understand its use of a «salt.» (According to the man page, a salt «is used to perturb the algorithm in one of 4096 different ways,» but why might that be useful?) As implied by that man page, you’ll likely want to put

#define _XOPEN_SOURCE
#include <unistd.h>
at the top of your file. Moreover, you’ll want to link with -lcrypt, as by compiling not with make but with:

clang -o crack crack.c -lcrypt
You might also want to read up on C’s support for file I/O, as there’s quite a number of English words in /usr/share/dict/words in CS50 IDE that might (or might not) save your program some time. If that file seems to be missing, you can install it with:

sudo apt-get install -y wamerican
sibkedr
кто-нибудь может подсказать почему у простого на вид кода
#include <stdio.h>
#include <string.h>

int main(void)
{
char *x = "AA";
char y[2] = {'B', 'C'};
printf ("%s + word + %s\n", y, x);

}

такой необычный вывод
BCt@ + word + AA.
Откуда берется эти символы «t@» — ведь их нету в массиве y.
sibkedr
по задачнику hacker2 http://cdn.cs50.net/2015/fall/psets/2/hacker2/hacker2..
50% паролей взломал. Но считаю, что задачу решил. Т.к. сперва написал для взлома бруттофорс, т.е. перебор всех печатных символов для пароля не длиннее 8 символов. Все работает и даже находит пароль №9, если для бруттофорса ограничить перебор только числами. Иначе же, если перебирать все печатные символы (http://en.wikipedia.org/wiki/ASCII#ASCII_printable_ch..), как по условию задачи, то потребуется несколько лет, для пароля длинной 8 символов. Длиной 5 — пару месяцев. Пришлось для этого поделать замеры, расчеты. По пути разобраться как мерить время в Си, тем более что сейчас на 8 уровне JavaRash только что прошли.
Поэтому попробовал атаку словарем — результат ниже и время. Использовал 2 словаря (те что смог найти в интернете) по 2 млн примерно в каждом. На перебор обоих словарей уходит не более 10 секунд для каждого пароля. Хочется остальные взломать, но… надо или словари искать (кстати, может кто подскажет, ссылку даст) или другие методы изучать (что не есть цель, хотя конечно знаний в языке прибавляется при самостоятельном поиске и изучении). В целом взглянул иначе на составление паролей и почему на многих ресурсах требуется длина от 6 символов.

1) «HALRCq0IBXEPM» —-----------------------------------------------------------------------—
Encrypted password «HALRCq0IBXEPM» was not cracked with pass1.txt — time search was 5.689 sec
Encrypted password «HALRCq0IBXEPM» was not cracked with pass2.txt — time search was 3.019 sec

2) «50zPJlUFIYY0o» ###-— «50zPJlUFIYY0o» is «13» —-### was cracked with pass1.txt — time search was 0.293 sec
3) «50MxVjGD7EfY6» —-----------------------------------------------------------------------—
4) «50z2Htq2DN2qs» —-----------------------------------------------------------------------—
5) «50CMVwEqJXRUY» —-----------------------------------------------------------------------—
6) «50TGdEyijNDNY» ###-— «50TGdEyijNDNY» is «harvard» —-### was cracked with pass1.txt — time search was 2.824 sec
7) «50QykIulIPuKI» —-----------------------------------------------------------------------—
8) «50q.zrL5e0Sak» ###-— «50q.zrL5e0Sak» is «password» —-### was cracked with pass1.txt — time search was 3.638 sec
9) «50Bpa7n/23iug» ###-— «50Bpa7n/23iug» is «12345» —-### was cracked with pass1.txt — time search was 0.250 sec
10) «HAYRs6vZAb4wo» ###-— «HAYRs6vZAb4wo» is «password» —-### was cracked with pass1.txt — time search was 3.741 sec

И как решить. Из-за трудностей с английским долго доходило как делать. Что нужно брать слова, шифровать его с помощью той же соли что и в захешированном пароле (первые 2 символа) и сравнивать захешированный пароль и твой результат. Для этого нужно объявлять
#define _XOPEN_SOURCE
#include <unistd.h>
и запускать в терминале ~/workspace/hacker2/ $ clang crack.c -o crack -lcrypt (через обычный make не канает)
ну а в программе использовать функцию crypt(pass, salt)
Только зарегистрированные и авторизованные пользователи могут оставлять комментарии.