Парсер Хабра: 2020-12-06

суббота, 12 декабря 2020 г.

Чтобы на фотографиях на аттракционах никто не снимал маски, в парках «Диснейленда» их добавят цифровым способом

Фотография гостей аттракциона «Мир динозавров» после обработки и добавления цифровых защитных масок.

Когда тематические развлекательные парки «Диснейленд» вновь начали открываться свои двери в июле 2020 года, то компании Дисней пришлось соблюдать все необходимые правила по охране здоровья и безопасности посетителей от коронавируса. Основное требование заключалось в том, чтобы гости парков постоянно носили защитные маски.

Дисней также ввела дополнительные правила при фотографировании на аттракционах, согласно которым гости, которые попали в кадр и были без маски на лице или она была приспущена, не получат фотографии, сделанные системой PhotoPass во время поездки. Также эти фото будут удалены из раздела «Мои фотографии» в учетной записи My Disney Experience нарушителей правил.

Только гости, которые соблюдают все правила и не снимают лицевые маски на протяжении всего аттракциона, смогут увидеть свою фотографию, купить ее на месте или скачать.

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

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

Теперь такие гости окажутся в непростом положении, когда будут сняты фотокамерой аттракциона. Сейчас система не всегда корректно накладывает цифровые маски на каждое лицо, так что итоговая фотография может получиться не такой красивой, как могла быть, если бы гости были в своих масках. Вдобавок из-за дополнительной обработки, необходимой для этих фотографий, системе требуется некоторое время, чтобы разместить изображения в учетных записях My Disney Experience гостей-нарушителей.

Дисней надеется, что цифровые маски не только дадут всем гостям пользоваться системой PhotoPass, но и будут способствовать дисциплине поведения. Например, их внедрение поможет уменьшить распространение процесса мышления типа «обезьяна видит, обезьяна делает», из-за которого гости могут ошибочно полагать, что маски на аттракционах можно снимать.

Дисней добавила, что будет дорабатывать эту систему цифровых масок и внедрять ее во всех своих парках и парках партнеров.

Let's block ads! (Why?)

Разработка симулятора космического корабля Союз ТМА

Тренажёр предстартовой подготовки ТПК Союз ТМА. Фото: ЦПК им. Гагарина

Привет! Мы - команда симулятора Союз ТМА, программы, имитирующей орбитальный полёт космического аппарата Союз и Международной Космической Станции, сближение и стыковку КА с МКС, а также расстыковку и спуск. Всё это имитируется как в автоматическом (т.е. под управлением моделями бортовой аппаратуры Системы Управления Движением), так и в ручном режимах полёта, которые по своему алгоритмическому и логическому составу идентичны тем, что использовались на борту КА Союз ТМА.

Нами разработано программное обеспечение под названием "Моделирование и Управление" в среде C++ Builder 6. Почему именно в ней, а не в VS - это наш первый проект и ранее никто из нас не имел опыта в программировании, а тем более в тренажёростроении, поэтому для "пробы пера" была выбрана наиболее простая среда, но при этом код разрабатывается так, чтобы его можно было максимально быстро интегрировать в другую среду (Qt, VS).

В первую очередь мы решили разработать основные оконные формы для отладки работы алгоритмов ПО - журнал протоколирования событий, а также форматы, имитирующие бортовую аппаратуру, с которой взаимодействует космонавт во время выполнения программы полёта.

Первой формой была - "Ввод начальных условий". На данной форме вводятся все необходимые параметры для выставления начального состояния КА и МКС, минимальный набор начальных параметров состояния бортовых систем, оскулирующие элементы и др. параметры, необходимые для начала режима. Сам список какие именно параметры необходимы для моделирования столь сложной системы нам были неизвестны, но изучив статьи на данную тему, имеющиеся в интернете, а также пообщавшись с разработчиками тренажёров подготовки космонавтов мы выяснили приблизительный набор параметров, которые использует ЦПК им. Гагарина и НАСА для задания начальных условий режимов полёта.

В этот список входят несколько групп параметров:

Основные характеристики:
- Массив моментов инерции (Jxx, Jyy, Jzz, Jxy, Jyz, Jzx) - который необходим для математической модели движения. Вводится как для корабля, так и для станции.
- Масса корабля и станции (в кг).
- Координаты центра масс корабля и станции.
Параметры орбиты:
Параметры ориентации:
- Начальная система координат корабля и станции (инерциальная текущая или орбитальная СК).
- Углы (тангаж, крен, рыскание).
- Угловые скорости (Wx, Wy, Wz).
Параметры режима:
- Признаки занятости стыковочных узлов (наличие пристыкованных кораблей).
- Начальный режим работы Системы Управления Движением и Навигации.
- Конфигурация станции.
- Набор состояния признаков состояния бортовых систем корабля и станции.
- Дата и время начала режима.

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

Пользовательский интерфейс, а также набор и расположение параметров были позаимствованы у тренажёра ДОН Союз-ТМА, как единственные известные нам, по ходу разработки мы от них откажемся и разработаем свой пользовательский интерфейс, основываясь на задачах, поставленных перед симулятором и необходимых параметрах для моделирования.

Из-за обширного количества вводимых значений, в данный формат мы добавили возможность загрузки и сохранения параметров начальных условий в файл. Принцип сохранения и загрузки прост и использует дефолтные компоненты, такие как TSaveDialog и TOpenDialog. Данные сохраняются и загружаются в ini файл (TIniFile), что довольно удобно. Структура файла также разделена на группы в соответствии с логикой набора параметров начальных условий.

Все действия оператора (загрузка и сохранение, а также все возможные ошибки) протоколируются в журнал событий с указанием времени и описанием действия.

Квитанция о загрузке начальных условий из файла

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

// Структура для математических моделей
struct{
//// Д А Т А ////
TDateTime nu_day;                   // 2   Модельное время/дата
//// М К С ////
double vec_j2000_mks[3];                // 8   Массив вектора положения Ц.М. МКС в J2000 (X, Y, Z)
double vel_j2000_mks[3];                // 11  Массив скорости    Ц.М.    МКС    в J2000 (X, Y, Z)
double Q_mks[4];                        // 14  Массив компонентов кватерниона МКС                                             0  1  2
double w_j2000_mks[3];                  // 18  Массив вектора угловой скорости МКС относительно J2000 в проекциях на ССК РС (Wx Wy Wz)
double vec_mks_PC[3];                   // 21  Массив координат   Ц.М.    МКС    в  РС   (X, Y, Z)
double m_mk;                            // 24  Масса МКС
double mi_mks[3][3];                    // 25  Двумерный массив моментов инерции МКС (Jxx, Jxy, Jxz...)
//// Т К ////
double vec_j2000_tk[3];                 // 34  Массив вектора положения Ц.М. ТК в J2000 (X, Y, Z)
double vel_j2000_tk[3];                 // 37  Массив скорости    Ц.М.    ТК    в J2000 (X, Y, Z)                   0   1   2   3
double Q_tk[4];                         // 40  Массив компонентов кватерниона разворота ССК ТК относительно J2000 (Qs, Qx, Qy, Qz)
double w_j2000_tk[3];                   // 44  Массив вектора угловой скорости ТК относительно J2000 в проекциях на ССК ТК (Wx Wy Wz)
double vec_tk_TPK[3];                   // 47  Массив координат   Ц.М.    ТГК/ТПК    в  РС   (X, Y, Z)
double m_tk;                            // 50  Масса ТК
double mi_tk[3][3];                     // 51  Двумерный массив моментов инерции ТК (Jxx, Jxy, Jxz...)
//// M I S C ////
double vec_solar[3];                    // 60  Единичный вектор из центра J2000 на Солнце в проекциях на J2000 (ex, ey, ez)
unsigned long r_st_mks;                 // 63  Режим стабилизации МКС
unsigned long n_su_4_dk;                // 64  Номер стыковочного узла МКС, к которому выполняется причаливание ТК (резерв, не используется)
unsigned long nu_otor_switch_styk_dk;     // 65  № СУ, к которому пристыкован ТК (для задания состояния состыкованного ТК)
double tk_top_zap;                      // 66  Запас топлива ТК (КДУ О+Г)
double mks_top_zap;                     // 67  Запас топлива МКС (РС ОДУ О+Г)
unsigned long pr_doking;                // 68  Признак состыкованного состояния ТК и МКС по НУ
unsigned long nr_sudn;                  // 69  Начальный режим работы СУДН ТК
} NU_temp;

// Массив признаков УСО
static bool USO_Booled[20][16];         // Матрица УСО (разблюдовка в ТО_УСО п.п. 3.7)

После этого мы изучили некоторые статьи по разработке математических моделей бортовых систем космических аппаратов (Е. А. Микрин - Бортовые комплексы управления космическими аппаратами ISBN 5-7038-2178-9), а также различные технические документы на Союз ТМА (в основном SoyCOM) и составили список основного приборного состава оборудования, которое необходимо реализовать для минимального функционирования системы и отладки основных алгоритмов управления.

В качестве математической модели движения на первом этапе было решено использовать модель SGP4, переработанную под нужды симулятора (вместо входных параметров TLE - массив параметров НУ).

Из приборного состава в первую очередь был реализован Пульт Ручного Ввода Информации (ПРВИ) в UI исполнении, как он был реализован на пульте космонавтов "Нептун" корабля Союз-ТМ

Данный пульт предназначен для информационного обмена оператора с БЦВК "Аргон-16". На кораблях серии ТМА данный пульт был исполнен в программном обеспечении Интегрированного Пульта управления (ИнПУ).

Так как на первом этапе разработки симулятора не предполагалось использовать обмен с моделью ИнПУ, то было решено использовать встроенную модель пульта ПРВИ с сам симулятор.

Логика работы с пультом следующая: оператор последовательно заполняет цифровые Индикаторы Ручного Ввода Информации (ИРВИ) кроме 15-го индикатора (знак + / -), после чего выдает команду на исполнение кнопкой "ИСП" и после обработки введённой информации наблюдает ответ-квитанцию от БЦВК на ИРВИ. Все действия с данным прибором также логируются в журнал. С помощью ПРВИ можно:

Произвести чтение/запись уставочной информации (состояние логических признаков управляющих слов 16-разрядной ячейки памяти Аргона).
Управлять форматами дисплея (форматы отображения Блока Формирования Изображения).
Организовать динамический вывод информации на ИРВИ.
Чтение/запись восьмеричных или десятичных чисел в память Аргона.

Исходя из вышеперечисленного можно сказать, что данный формат позволяет производить полный информационный обмен с памятью БЦВК, что на этапе отладки модели БЦВК крайне важно.

Для облегчения восприятия информации и ввода вывода уставочной информации, начиная с кораблей серии Союз ТМА-М работу с ПРВИ упразднили, оставив лишь формат отображения ИнПУ "ПРВИ" (индекс 2Ф46), на который выведены основные управляющие слова (В1-ТА1) для контроля их состояния (при выполнении штатной программы полёта, изменение состояния логических признаков происходит по Командной Радио Линии (КРЛ) с Земли группой ГОГУ). Ниже представлен скриншот формата ПРВИ корабля Союз МС с выведенным на экран состоянием логических признаков управляющего слова А20.

Для удобства работы с кодом и последующей миграции кода из C++ Builder 6 в среду Visual Studio (планируется, что итоговое приложение будет MFC + OpenGL в качестве графического движка для системы визуализации) каждый формат имеет помимо своего файла формы (***_form.cpp) также файл с логикой, где описаны все процедуры и функции для данной системы/прибора. Логика работы прибора ПРВИ в симуляторе следующая:

Вначале пользователь должен включить прибор, нажав клавишу ON, тем самым он выставит логический признак brvi_on = true;

void __fastcall TIrBrForm::brvi_on_btnClick(TObject *Sender)
{
brvi_on=true;           // Признак включения ПРВИ
Panel1->Color=clLime;   // Зажигаем индикатор состояния прибора зеленым цветом
}

Далее используя один из кодов ввода-вывода необходимо ввести последовательно режим, адрес и число, а также, если необходимо, то и знак. Знак можно ввести на любом этапе заполнения цифровых индикаторов. Ниже описаны коды ввода-вывода информации, актуальные для ПрО Союз ТМА №228

Операция	Код
Одиночный ввод десятичных чисел	14
Одиночный ввод восьмеричных чисел	15
Групповой ввод десятичных чисел	17
Групповой ввод восьмеричных чисел	18
Запись "0" в заданный разряд ячейки ОЗУ	30
Запись "1" в заданный разряд ячейки ОЗУ	31

Операция	Код
Одиночный вывод десятичных чисел	24
Одиночный вывод восьмеричных чисел	25
Групповой вывод десятичных чисел	27
Групповой вывод восьмеричных чисел	28
Динамический вывод десятичных чисел	04
Динамический вывод восьмеричных чисел	05

В ПО каждый индикатор является компонентом TPanel, где заполняется свойство Caption. При нажатии на какую-либо цифровую клавишу последовательно проверяется занятость каждого индикатора и заполняется последний свободный индикатор. Ниже приведен участок кода обработки нажатия цифровой клавиши "1":

void __fastcall TIrBrForm::brvi_btn_1Click(TObject *Sender)
{
if(brvi_on){
USO_BitType[16][3] = 0111;
if(i1->Caption=="")
        i1->Caption="1";
else if(i2->Caption=="")
        i2->Caption="1";
else if(i3->Caption=="")
        i3->Caption="1";
else if(i4->Caption=="")
        i4->Caption="1";
else if(i5->Caption=="")
        i5->Caption="1";
else if(i6->Caption=="")
        i6->Caption="1";
else if(i7->Caption=="")
        i7->Caption="1";
else if(i8->Caption=="")
        i8->Caption="1";
else if(i9->Caption=="")
        i9->Caption="1";
else if(i10->Caption=="")
        i10->Caption="1";
else if(i11->Caption=="")
        i11->Caption="1";
else if(i12->Caption=="")
        i12->Caption="1";
else if(i13->Caption=="")
        i13->Caption="1";
else if(i14->Caption=="")
        i14->Caption="1";
else {}
}
}

Мы не смогли разобраться, как записать это в виде цикла for, поэтому сделали таким образом. По такой же логике работают обработчики и на остальных клавишах. Если необходимо очистить индикаторы, то для этого надо нажать клавишу "СБР", а если убрать последний введенный индикатор, то клавишу "ГАШ".

После окончания заполнения индикаторов необходимо отправить введенные значения на обработку в БЦВК, ниже представлен код обработчика клавиши ИСП:

void __fastcall TIrBrForm::isp_btnClick(TObject *Sender)
{
if(brvi_on) { // Если БРВИ вкл
if(i1->Caption==""&&i2->Caption==""){  // Если первый и второй индикаторы пустые,
i1->Caption=="A";     // Тогда сообщение АА
i2->Caption=="A";
JPS(3,is_irvi,is_operator,"АА","");  // и лог в журнал
} else {              // или (если 1И и 2И не пустые)
AnsiString brvi_msg = i1->Caption+i2->Caption+i3->Caption+i4->Caption+    // Создаем строку текущего состояния И ИРВИ
i5->Caption+i6->Caption+i7->Caption+i8->Caption+i9->Caption+i10->Caption+
i11->Caption+i12->Caption+i13->Caption+i14->Caption+i15->Caption;
JPS(1,is_operator,is_irvi,brvi_msg,"");
Timer1->Enabled=true;  // Включаем таймер задержки индикации
// Обнуляем индикаторы перед индикацией
i1->Caption="";
i2->Caption="";
i3->Caption="";
i4->Caption="";
i5->Caption="";
i6->Caption="";
i7->Caption="";
i8->Caption="";
i9->Caption="";
i10->Caption="";
i11->Caption="";
i12->Caption="";
i13->Caption="";
i14->Caption="";
i15->Caption="";

irvi_string = brvi_msg; // Присваиваем глобальной переменной значение ИРВИ

ChekIrvi(irvi_string); }} else  // Если БРВИ выключен
JPS(3,is_miu,is_operator,cmd_brvi_error,"");   // Ошибка в Журнал
}

Здесь мы собираем из индикаторов строку, которую после присваиваем глобальной AnsiString переменной irvi_string. Процедура ChekIrvi принимает в качестве аргумента сформированную строку и производит с ней следующие операции:

void ChekIrvi (AnsiString irvi_str){
if(irvi_str.IsEmpty())JPS(3,is_miu,is_operator,"Пустой ввод!",""); else {
irvi_type.mode = StrToInt(irvi_str.SubString(1,2)); // Вырезаем первые два символа строки ирви "режим"
switch (irvi_type.mode) {   // Обработчик режима
        case 00: /* Приоритетный или принудительный режим выдачи пр-м 1 - 4 */ break;
        case 04: /* Динамический вывод 10-х чисел */ break;
        case 05: /* Динамический вывод 8-х чисел */ break;
        case 10: /* Ввод уставки РУС */   break;           // Arg addr RUS AUS data?
        case 11: /* Ввод уставки АУС 1-й группы */  break;
        case 12: /* Ввод уставки АУС 2-й группы */  break;
        case 14: /* Одиночный ввод 10-х чисел */                       // Если режим 14, то
                 if((irvi_str.SubString(3,5)).IsEmpty())JPS(3,is_miu,is_operator,"Пустой адрес!",""); else {
                 irvi_type.addr = StrToInt(irvi_str.SubString(3,5));   // Присваиваем значение адреса
                 if(CorrectAddr(irvi_type.addr)) {                     // Проверяем корректность адреса, если корректен, то
                 if((irvi_str.SubString(8,7)).IsEmpty())JPS(3,is_miu,is_operator,"Пустое число!",""); else {
                 irvi_type.value = StrToInt(irvi_str.SubString(8,7));  // Присваиваем значение
                 ArgonMemoryType[irvi_type.addr] = irvi_type.value;    // Записываем его в ячейку памяти Аргона
                 SetItvi(irvi_type.mode,irvi_type.addr,ArgonMemoryType[irvi_type.addr], irvi_type.z );   // Выставляем результат на ИРВИ
                 JPS(4,is_argon,is_irvi,"Запись числа "+               // Логируем результат (от имени Аргона)
                 IntToStr(irvi_type.value)+" по адресу "+IntToStr(irvi_type.addr),"");}}
                 else {                                                 // Если адрес не корректен ,то
                 irvi_err = true;
                 JPS(3,is_argon,is_operator,arg_addr_error,"");     } }  // Логируем превышение допустимого значения памяти А16
                 break;
        case 15: /* Одиночный ввод 8-х чисел */  break;
        case 17: /* Групповой ввод 10-х чисел */ break;
        case 18: /* Групповой ввод 8-х чисел */
                // irvi_type.addr = StrToInt(irvi_str.SubString(3,5));   // Присваиваем значение адреса
                 // if(CorrectAddr(irvi_type.addr)) {                    // Проверяем корректность адреса, если корректен, то
                 //irvi_type.value = StrToInt(irvi_str.SubString(8,7));  // Присваиваем значение
                // ArgonMemoryType[irvi_type.addr] = irvi_type.value;   // Записываем его в ячейку памяти Аргона
                 //SetItvi(irvi_type.mode,(irvi_type.addr)+1,ArgonMemoryType[irvi_type.addr], irvi_type.z );   // Выставляем результат на ИРВИ
                 //mode18act=true;
                 break;
        case 21: /* Вывод уставки АУС 1-й группы */ break;
        case 22: /* Вывод уставки АУС 2-й группы */ break;
        case 24: /* Одиночный вывод 10-х чисел */                      // Если режим 24, то
                 irvi_type.addr = StrToInt(irvi_str.SubString(3,5));   // Присваиваем значение адреса временной переменной
                 if(CorrectAddr(irvi_type.addr)) {                     // Проверяем корректность адреса, если корректен, то
                 SetItvi(irvi_type.mode,irvi_type.addr,ArgonMemoryType[irvi_type.addr], irvi_type.z ); }  // Выставляем результат на ИРВИ
                 else   {                                               // Если адрес не корректен ,то
                 irvi_err = true;
                 JPS(3,is_argon,is_operator,arg_addr_error,"");   }     // Логируем превышение допустимого значения памяти А16
                 break;
        case 25: /* Одиночный вывод 8-х чисел */ break;
        case 27: /* Групповой вывод 10-х чисел */ break;
        case 28: /* Групповой вывод 8-х чисел  */break;
        case 30: /* Изменение состояния признака в слове - запись единицы */
                 irvi_type.addr = StrToInt(irvi_str.SubString(3,5));   // Присваиваем значение адреса временной переменной
                 if(CorrectAddr(irvi_type.addr)) {                     // Проверяем корректность адреса, если корректен, то
                 irvi_type.value = StrToInt(irvi_str.SubString(8,7));  // Присваиваем значение
                 mode_30(irvi_type.addr,irvi_type.value); }             // Выставляем результат на ИРВИ
                 else   {                                              // Если адрес не корректен ,то
                 irvi_err = true;
                 JPS(3,is_argon,is_operator,arg_addr_error,"");   }    // Логируем превышение допустимого значения памяти А16
                 break;
        case 31: /* Изменение состояния признака в слове - запись нуля */
                 irvi_type.addr = StrToInt(irvi_str.SubString(3,5));   // Присваиваем значение адреса временной переменной
                 if(CorrectAddr(irvi_type.addr)) {                     // Проверяем корректность адреса, если корректен, то
                 irvi_type.value = StrToInt(irvi_str.SubString(8,7));  // Присваиваем значение
                 mode_31(irvi_type.addr,irvi_type.value); }             // Выставляем результат на ИРВИ
                 else   {                                              // Если адрес не корректен ,то
                 irvi_err = true;
                 JPS(3,is_argon,is_operator,arg_addr_error,"");   }    // Логируем превышение допустимого значения памяти А16
                 break;
        case 40: /*  */ break;
        case 41: /*  */ break;
        case 42: /*  */ break;
        case 43: /*  */ break;
        case 44: /*  */ break;
        case 45: /*  */ break;
        case 46: /*  */ break;
        case 48: /* Сверка времени */
        break;
        default: irvi_err = true;       // Флаг ошибки (для индикации на ИРВИ)
                 JPS(3,is_argon,is_irvi,"АА","");        // Логируем ошибку о несуществующем режиме
                 JPS(3,is_miu,is_operator,"Несуществующий режим!","");
        irvi_type.addr = StrToInt(irvi_str.SubString(3,5));
        irvi_type.value = StrToInt(irvi_str.SubString(8,7));
        break;
} } }

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

Вся необходимая информация (инструкции, аварии, состояние логических признаков и др.) хранится в ячейках памяти и мы можем ее вызвать в любое время используя формат ПРВИ.

Это был первый формат относящийся к модели БЦВК "Аргон-16", но его оказалось недостаточно и в последствии был разработан еще один формат для отладки модели БЦВК "Отладка А16", скриншот которого представлен ниже:

На нём можно наблюдать виртуальные клавиши принудительной выдачи команд в БЦВК (имитации релейных команд для отладки некоторых процедур и алгоритмов), вывести число из ОЗУ без использования ПРВИ (если ПРВИ занят, т.к. с ним могут работать 2 оператора - обмен по UDP), наблюдать текущее значение глобальной переменной ИРВИ, наблюдать статусное окно выбранных каналов БЦВК (т.к. он работает по мажоритарной схеме 2 из 3) и др. Пустые поля по мере разработки будут заполнятся отладочными командами. Все компоненты TLabel выводятся в обработчике таймера, который каждый тик присваивает им состояние переменных.

Этот формат позволит нам отслеживать работу алгоритмов БЦВК (как самых сложных в реализации) и прерывать работу модели при нештатной работе (отклонении от нормы).

Следующими основными форматами, без которых невозможно управление кораблём Союз, являются - КСПл и КСПп. Около половины времени работы космонавта с ПрО пульта "Нептун-МЭ" приходится именно на эти форматы. На них представлены основные команды выдаваемые оператором в бортовые системы корабля - включение и пуск БЦВК, команды управления двигательной установкой, управление ССВП и др. Ниже представлены форматы КСПл и КСПп разработанные для симулятора:

Данные форматы по своему информационному обеспечению идентичны одноименным форматам используемым в ПрО и ИО ИнПУ, что также позволяет работать с ними как с штатными форматами отображения, для сравнения - ниже скриншот штатного формата КСПл корабля Союз ТМА №219 (ПО № 5.19, ИО № 5.1)

Логика работы с данным форматом уникальна и разработана Тяпченко Ю.А. Основным преимуществом данного типа пульта является матричный способ выдачи команд и развернутая форма представления информации. С точки зрения эргономики это довольно удобный способ представления большого количества команд, при малом количестве органов взаимодействия. Логика работы с данным форматом следующая - оператор выбирает вначале строку (букву) и выдает ее, буква загорается и разрешается выбор столбца (цифры), где нечётная цифра включает команду, а чётная ее выключает. К примеру, чтобы выдать команду на включение РУД, необходимо вначале нажать клавишу "В", а потом "7". Таким образом будет подана команда на включение питания ручки управления движением, а в пульт придёт обратная квитанция об успешности исполнения команды, которая "зажжёт" транспарант светло зеленым цветом.

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

Это обозначает, что если команда без сигнализации - значит обратной квитанции и загорания соответствующего транспаранта не будет, а если команда только прямая, значит при выдаче чётной цифры (выключения) команда не пройдет и транспарант не погаснет. Обычно эти команды выключаются другими командами, к примеру для снятия признака выбора К11 "РРЖ 4С" необходимо выдать Л15 "РРЖ 15С" или Л13 "РРЖ 8С".

В симуляторе логика КСП реализована следующим образом. Объявлен двумерный булевый массив

static bool KSP_Booled[16][9];

который хранит состояние команд, если мы выдаем ту или иную команду КСП, то присваиваем соответствующему элементу значение true, которое снимается обработчиком получившей его системы. К примеру при выдаче команды А7 "СДД ОТКЛ" мы выставляем признак KSP_Booled[0][6]=true; , основной обработчик УСО каждый тик обрабатывает весь массив и при KSP_Booled[0][6]=1 сразу снимает эту команду и посылает команду в КДУ и другие системы соответствующие признаки, в это время в КСП стоит обработчик квитанций УСО, который в свою очередь опрашивает каждый элемент массива УСО и если видит ответную квитанцию об успешном отключении сигнальных датчиков СДД от системы управления, зажигает транспарант "СДД ОТКЛ", ниже представлен код обработки этой команды:

// Модуль КСПл, обработчик нажатия цифры 7
 ...
   if (KSP_Let[0]){ // А                              Если выбранна буква А
   KSP_Booled[0][6]=true;                          // Тогда выставляем признак А7 - правда
   JPS(1,is_operator,is_miu,is_ksp,"А7"); } else   // Логируем выдачу команды
 ... 

// Модуль uso_model.cpp процедура USO_work
 ...
     if(KSP_Booled[0][6]) { // A 7
        KSP_Booled[0][6] = false;
        // 95 Исключение СДД из схемы управления
        USO_Booled[0][3]=true;
        kdu_sdd = false;
     }
 ...
 
// Модуль КСПл - тик таймера индикации
 ...
  if(USO_Booled[0][3]){  // KSP A7
  A7_LABEL->Color=clLime;
  A7_LABEL->Font->Color=clBlack;  } else {
  A7_LABEL->Color=clGreen;
  A7_LABEL->Font->Color=clYellow; }
 ...

Таким образом мы реализуем штатную логику работы с КСП и УСО, конечно если тут есть люди разбирающиеся в УСО корабля Союз, которые нашли ошибку в нашей интерпретации логики работы с КСП, прошу нас поправить, т.к. у нас не имеется материалов по УСО и данную логику мы построили изучая работу моделей ИнПУ и руководство по работу с системой Нептун-МЭ.

Я думаю это довольно много информации для одного поста, поэтому остальные форматы опишу в следующем посте.

Let's block ads! (Why?)

Программисты разгадали очередной шифр убийцы Зодиака спустя полвека

_{Фото: zodiackillerfacts.com}

Международная команда взломщиков, в которую входили специалисты из США, Австралии и Бельгии, смогла разгадать шифр серийного убийцы по прозвищу Зодиак, который так и не был пойман. Этому шифру 51 год. Зодиак отправил его в американскую газету San Francisco Chronicle в 1969 году.

Текст «Шифра 340», названного так за количество содержащихся слов, гласит: «Я надеюсь, что вам очень весело пытаться поймать меня. В том телешоу был не я. Я не боюсь газовой камеры, потому что она отправит меня в рай еще раньше, потому что теперь у меня достаточно рабов, чтобы работать на меня. Они боятся смерти, а я не боюсь». Речь идет о телешоу The Jim Dunbar Show от 22 октября 1969 года, в эфир которого дозвонился неизвестный, представившийся Зодиаком. Текст послания был отправлен спустя две недели после этого шоу.

При работе над шифром команда надеялась, что убийца раскроет в тексте свое имя.

Один из исследователей, программист Дэвид Оранчак, работал над головоломкой убийцы почти 15 лет. Он хотел создать программу для расшифровки послания, но попытки были неудачными. Оранчак даже организовал веб-сайт ZodiacKillerCiphers.com с информацией о шифрах.

Другой участник группы, программист Ярл Ван Эйке, создал AZdecrypt, инструмент, который позволил ему установить мировой рекорд по расшифровке подстановкой биграмм.

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

_{Фото: Дэвид Оранчак, Сэм Блэйк, Ярл Ван Эйке/zodiackillerfacts.com}

Первое разгаданное в 1969 году послание «Шифр 408» имело шифрование, при котором необходимо было подобрать буквы, которые обозначались определенными символами. Оно по смыслу согласуется с новой расшифровкой. В первом послании убийца написал, что убивал людей, чтобы «собрать рабов», которые могли бы служить ему во время его загробной жизни в «раю». Зодиак включал в текст те же ошибки, используя слова «рай» и «рабы».

_{Фото: zodiackillerfacts.com}

В последнем «Шифре 340» слова выстраивались по диагонали вниз, иногда смещаясь в сторону по столбцу. По словам Оранчака, подобные схемы можно было найти в шифрах американского военного руководства 1950-х годов.

Два послания Зодиака пока остаются неразгаданными. Утверждается, что в одном из них убийца все-таки называет свое имя.

Зодиак орудовал в Калифорнии в 1960-х. Его так и не арестовали и не идентифицировали. При этом убийца развлекался тем, что отправлял в редакции газет зашифрованные послания о себе. В одном из них он сообщил, что убил 37 человек. При этом официально полиция США подтвердила только семь эпизодов с его участием.

См. также:

Let's block ads! (Why?)

Russian AI Cup 2019. 4 место, почти не умея программировать или о пользе soft skills

Данная статья рассмотрит процесс моего участия с “тёмной” стороны - менеджера проектов. Немного о мотивации, немого о времени и приоритетах. За “светлой” стороной технических деталей лучше обратится к статьям T1024, Lama, SilentNox.

Надеюсь данной статьёй, во-первых, приободрить тех, кто собирается участвовать первый раз и развеять мысли, что “там все призы уже давно поделены между топами”, а, во-вторых, может быть кому-то помочь в работе.

Кратко для тех кому лень читать: поток и работа с мотивацией, приоритизация и адаптация, сделать лучше, чем было, а не идеально.

О чемпионате

В 2019 году задачей было написать бота для 2d шутера. Вот пример видео от Lama:

Чемпионат проходит в несколько этапов, каждый длинной в одну неделю:

Бета тестирование.
Первый этап. Перезапуск с незначительными изменениями правил по результатам теста. Боты регулярно сражаются друг с другом в “песочнице”. В конце недели первый раунд.
Второй этап. Правила игры усложняются, у каждого бота в управлении уже не один, а два человечка. В “песочнице” проходят бои по правилам и первого, и второго этапа. В конце недели второй раунд соревнования - участвуют 200 победителей первого раунда+около 60 лучших из “песочницы”.
Финальный раунд. Очередное изменение правил - карты становятся сложнее. Без поиска пути на них делать нечего. Бои в песочнице по правилам всех раундов. Финал - 50 победителей второго раунда+10 лучших песочницы. Призовые первые 6 мест.

Какие нужны навыки?

Кажется очевидным, что для победы необходимо:

Хорошо уметь программировать, чтобы это ни значило.
Иметь опыт участия в подобных соревнованиях, желательно в RAIC прошлых лет.
Начать со старта беты - это дополнительная неделя.

Заканчивается первый этап (прошла примерно половина времени) - присоединяется человек, который ни дня не работал программистом и только иногда писал скриптики для автоматизации работы, а в соревновании участвовал только много лет назад в школе на pascal. Ваши ставки на место? Мои ставки до того, как я понял, о чём вообще речь, были: “ну я потыкаю, как оно вообще работает, и хватит”, а после первого знакомства - "надо войти в топ 250 - во второй раунд и получить футболку, как участник второго раунда". У меня большое самомнение : )

Посмотрим ещё раз на задачу. Нас просят не написать чистый алгоритм - “Вася варит n яиц в m кастрюлях”. Это задача уровня выше - вот цель, вот правила, вот ограничения. Вам нужно за имеющееся время написать наилучшее решение. Тут можно выделить много подзадач из серии “У вас оружие с параметрами p1, у врага c параметрами p2 - найдите оптимальную для вас дистанцию стрельбы”. Т.е. помимо решения отдельных маленьких подзадач, нам нужно их самому правильно сформулировать и приоритизировать. А потом выбрать нужный баланс между качеством и трудозатратами с учётом ограниченного времени.

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

Итого для данного чемпионата добавились два важных навыка:

Гибкость, скорость реакции на изменения мира, готовность изменять стратегию.
Постановка и выбор наиболее важных задач.

Хм… а это точно чемпионат не для тимлидов, аналитиков и менеджеров? Ах, задачи придётся выполнять самому, а не отдавать программистам.

Итак, очевидно, что времени для идеального исполнения мне не хватает. Судя по сложности задачи, предположу, что и большинству участников не хватит тоже, даже несмотря на то, что у них 4 недели, а не 2. Итак мы имеем функцию от времени f(t)->max. Осталось понять что мы будем максимизировать. На первый взгляд, финальное место в рейтинге/крутость бота. И в слагаемых функции будут всякие параметры стратегии. Допустим уклонение от пуль, стрельба, поиск пути. Распределяем время на разработку по этим параметрам - и мы победили : ) Ладно, добавим “фундаментальные исследования” - изучение платформы, подтягивание знаний ЯП, рефакторинг и оптимизацию. Но люди не машины и в разных условиях одна и та же задача может занять и 2 и 8 часов. Поэтому нам нужно также решить задачу поддержания высокой производительности. Поэтому первую часть чемпионата я буду максимизировать… удовольствие от участия, для повышения мотивации продолжать. А место в рейтинге будет всего лишь замечательным искусственным индикатором эффективности, рост рейтинга - быстрая положительная обратная связь.

Вы показалось, что разницы нет? Она в том, что для первого случая нам достаточно победить в конце, а для второго нам необходимы постоянные маленькие победы.

Из-за стартового штрафа в 2 недели остаётся только работать в “потоке”. А здесь тонкая грань работы с мотивацией. Судя по чату, часть людей выгорела до конца чемпионата. Грубо говоря на решение задачи мы тратим ресурс “мотивация”, а в случае успешного решения его получаем. Я начинаю с дефицитом мотивации, поэтому на решение большой задачи её не хватит.

Платформа

Вот тут большой респект организаторам.

На самом деле платформа очень игрофицированна. И все 4 типа фана, и эстетика с отсылкой на старые игры, и всяческое подкрепление мотивации (от быстрой обратной связи до последовательного роста сложности), внешняя мотивация, которая и работает и не перебивает внутреннюю.

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

Базовая работающая стратегия. “Хватай пушку, беги к врагу и стреляй”. На разных ЯП.
Визуализатор (local runner), который позволяет сыграть самому мышкой и клавиатурой против бота или же запустить своего бота против стартовой стратегии/другой версии своего бота. И показывает собственно сам бой.
Простые правила первого раунда. Один юнит и простая карта.
Песочница, где залитые стратегии регулярно сражаются друг с другом и результат отражается в виде рейтинга.

Это дает возможность за 10 минут добавить к базовой стратегии, допустим, сбор аптечек и сразу же увидеть результат - моментальная положительная обратная связь. Причём по нескольким каналам восприятия: и сам сбор аптечек, и звук сбора и возросший шанс на победу - чаще побеждает бот. Что в свою очередь даёт мозгу информацию “А это не так и сложно. Если за 10 минут мы уже столького добились, то давай попробуем вложить больше времени, прикинь какой тогда эффект будет?”.

Вместо прямого подхода: “Изучи API, все правила, алгоритмы, связи, а потом уже что-то сделаешь и получишь результат”, мы имеем “сделай чуток и получишь небольшой результат, изучи правила и сможешь получить результат побольше, углубились в модель и результат станет ещё больше.”

Да нас сама платформа подталкивает работать в потоке! Осталось только помочь ей!

Немного теории о “потоке” и модели Фогга в моём кратком изложении.

Поток М.Чиксентмихайи. Есть субъективная сложность задачи и субъективная оценка своих навыков. В зависимости от соотношения этих параметров, задачи вызывают разные эмоции и состояния.

Сложность >> Навыка - тревога
Сложность << Навыка - скука.
Сложность ~ Навыку - потоковое состояние - максимальная концентрация на задаче, чувство потери времени, озарения и т.п. Но ресурсозатратно для организма.

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

Для потока, конечно же, недостаточно только адекватной сложности, но чтобы не увеличивать объём статьи я просто скажу, что задача и система чемпионата отлично подходит для потокового состояния и обладает необходимыми критериями. Что же нужно нам: усложнять задачи по мере роста навыков, обеспечить себе быструю обратную связь на усилия, обеспечить какое-то измерение прогресса.

В теории Фогга говорится что для совершения действия необходимо:

чтобы мотивация была выше, чем затраты усилий на за задачу;
толчкок/тригер/напоминание для совершения действия.

Можно создавать события повышающие мотивацию, снижающие (субъективную) сложность и просто напоминания.

Для завершения теоретической базы хочется добавить ещё:

Не ассоциировать качества своей личности с результатом. Т.е. если вы не заняли первое место, это не значит, что вы тупой : ) Именно этот момент часто останавливает людей от серьёзного включения. При такой установке логичнее не прикладывать максимум усилий. Чтобы оставить себе иллюзию, что если бы я действительно старался бы, то победил. Сошлюсь тут на свою же статью (список более серьезной литературы в конце приложенной статьи).
Фундаментальная ошибка атрибуции. Чтобы здраво оценивать свои достижения и достижения других и своевременно реагировать.
Путь героя Кэмпбелла. В кратком виде, он отлично ложится на мотивации, отношение, серьёзность участника, а также предупреждает об основных моментах отсева. Вход (а что это, а зачем, а оно мне надо?), дорога испытаний (первые действия, решение первых проблем, первые результаты), встреча с богиней/женщина-искусительница (оказывается тут ещё дофига всего делать, может ну его? оно того не стоит? Около запуска правил второго раунда), примирение с отцом - основной этап.

Программист VS менеджер

Так получилось, что в качестве аватарки я использовал логотип моего проекта по развитию soft skills, поэтому лично для меня этот чемпионат ещё превратился в проверку гипотезы могу ли я за счёт soft skills компенсировать недостаток hard skills.

Для решения данной задачи я выделю в себе внутреннего программиста и внутреннего менеджера. На мой взгляд, многие места ниже моего обусловлены, в том числе, победой программиста над менеджером. Для простоты представьте, что программист - это такой junior: глаза горят, идей много, готов сидеть ночами и осваивать всё подряд, практический опыт… странный.

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

Что происходит при этих словах в голове у менеджера - крутится абстрактный счётчик сложности задачи, который резко отодвигает хоть какой-то результат. Напомним, что наш программист jun и ничего ещё не умеет, но верит, что быстро разберётся. Если бы я так начал, то скорее всего помер бы, погребённый сложностью своей модели и количеством неизведанного. Результата мало, сложность постоянно растёт, время кончается.

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

Общий подход менеджера - не надо решать задачу идеально, надо решать по наилучшему соотношения польза/время.

История участия

Начало. Тут какое-то соревнование идёт? Выглядит симпатично, давай глянем. Погружение низкое. Навык и мотивация тоже. Задача: решить участвовать или нет.

Смешной факт - глянув на призы я сказал, что ну, пожалуй, возьму четвёртое место. Первые два, наверное, без шансов, за третье дают iPad, а я в них на работе наигрался, а за четвёртое умные часы. Тоже нафиг не нужны, но смешно поиграться будет. Конечно это была больше шутка, т.к. я сомневался, что и в топ 50 войду.

Открываю пример кода стартовой стратегии на Python… И половину не понимаю. Программист: “Тут пипец сложно, это не мой уровень только разбираться во всём будем неделю. А и так уже 2 недели соревнования прошло. Пошли отсюда.”. Менеджер: “Давай глянем другие примеры, общая логика-то понятна”.

К счастью пример на C# оказался написан попроще, а там уже в Python стало понятно. Но что делать? После игры со стартовой стратегией кажется, что она и так уже играет идеально. Быстрый анализ выдал - “подбирай аптечки” и “уворачивайся от пуль”. Программист, конечно же захотел всё это реализовать, а в идеале увязать в единую логику, только неясно как. Менеджер: давай вначале аптечки сделаем. Аптечки делались копированием кода подбора оружия и заменой пары значений. 10 минут, запускаем - оно работает! Моего уровня достаточно для написания RAIC!

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

Время уворачиваться от пуль.

П: хочет писать идеальный код уворота от всех пуль.

М: хм… а давай прикинем, на каком расстоянии нам держаться от врага, чтобы успеть увернуться, и будем стараться его соблюдать, а дальше прикинем, что будет, если за время подлёта пули мы могли бы сместится на любое из 6 направлений. Если что-то позволит избежать встречи с пулей, то смещайся туда.

П: но… там же может быть стена, или я не могу сейчас прыгать или ещё что.

М: просто игнорируй это.

П: это же часто будет не срабатывать!

М: пусть это будет срабатывать в 50% случаев. Для простоты будем считать, что в среднем нужно попасть по врагу 4 раза, вероятность попасть 20%, скорострельность одинаковая. Тогда у врага шанс попасть в нас 10%, а у нас в него 20%. Это даст нам около 84% побед, при куда меньших затратах времени. Наша же задача побеждать не всегда, а чаще, чем оппонент. А оставшиеся 16% потребуют для реализации куда больше времени, чем этот алгоритм, но дадут куда меньше пользы на данном этапе.

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

//использование дедлайна для стимуляции - приём известный всем студентам.

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

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

П: Ну это позор, такое выкатывать нельзя, сейчас напишем детальный обсчёт куда полетит снаряд, правда он вылетает в случайном направлении из диапазона, но это тоже можно обсчитать.

М: пф, запретим юниту брать базуку, пусть берёт всё остальное.

//5 минут, +1 доп условие и резкий буст к победам.

Это дало: резкое усиление мотивации. Показало, что не всё так сложно и как минимум в первую половину участников мы уже легко попадаем. Нужно участвовать!

Стратегия и правда легко прошла после открытия песочницы в понедельник с 1000+места в топ 300. Несколько напоминает MVP.

Дорога испытаний. Началась песочница второго раунда. 5 дней боты сражаются друг с другом, а потом победители первого раунда и 60 других лучших песочницы примут участие во втором раунде. Задача понятна - попасть во второй раунд. Т.е. войти в эти 60 за 5 дней.

К сожалению для меня задача усложнилась, теперь в бою часто участвуют уже 2 юнита с одной стороны. Все-то научились одним управлять в первую неделю, а теперь время командной работы. А я ещё с одним не разобрался. Посмотрев на игры, я выделил следующие зоны развития: Стрельба, уворот, контроль поля, командная работа, доп фичи. 0% реализации в любой зоне, кроме доп фич, даёт резкое падение эффективности, при этом до 20-30% доводится довольно быстро, и даёт сильный взлёт. Т.е. 20% стрельба и 20% уворот выгоднее, чем 90% уворот и 0% стрельба (почти невозможно победить не стреляя).

Текущая задача говорит, что основные конкуренты сейчас не топы, а “соседи” по рейтингу. Чтобы гарантированно уложится во время, надо сосредоточится на максимальном усилении против них, желательно максимально быстро.

Командной работы тут ни у кого нормальной нет и выигрыш по оценкам она пока даёт небольшой. Быстро пилю свои 10% (не стреляй в спину своему) и возвращаюсь к другим доработкам.

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

Во вторник занимаю двухсотые места в рейтинге. В среду вхожу в топ 100 - шанс не попасть во второй раунд мизерный. Задача выполнена.

Что мы имели на этом этапе. Много мелких и относительно быстрых исправлений, дающих очень быструю обратную связь - и визуально видно действие ботиков и рейтинг быстро даёт информацию. Всё это позволяет держаться в потоке и даёт постоянные позитивные подкрепления. Текущее место наглядно показало, что мои текущие способности вполне ничего и не боги тут участвуют. А это сместило субъективные навыки повыше, а относительную сложность задач пониже, что дало мне возможность легче браться за более сложные задачи.

Теперь задача во втором раунде войти в топ 50, чтобы попасть в финал. Всё в базовом виде реализовано, общая логика работы понятна. Мотивация высокая и не требуется постоянное подкрепление. Можно теперь потратить время на “фундаментальные исследования” и вложения в будущее - переписать код понятнее, сделать сложные расчёты. Где-то здесь были переходы к более универсальным моделям, понятной структуре. Здесь же я допустил ошибку и начал писать симуляцию на 60 тиков (ходов) вперёд перебором. Каждый ход есть 9 вариантов действия юнита. На первый ход 9 вариантов, на второй 81 и т.д. Представляете порядок 9^60 (и это только для одного юнита, а в идеале считать все перемещения всех четырёх)? Это очень много - не рассчитывается за адекватное время. Ну а мои программист и менеджер проглядели этот момент. Программист только теоретически знает о сложности алгоритмов, а менеджеру кажется логичным подход когда компьютер считает(работает), а человек думает. Знакомые настоящие программисты когда я им потом рассказывал этот момент громко ржали : )

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

Утро пятницы, код стал упорядоченнее, некоторые функции уже выглядят не как мешок “ifов” и магических циферок

//“не нравится мне, что бот жмётся к краю карты - там увороты хуже работают и его там расстреливают, - сделай, чтобы он старался захватывать минимум четверть поля. Как? Повысь агрессивность, если “позади Москва”.

Надо дальше писать - ночью стартует раунд! Но 6 дней потока заметно сказываются. Есть риск, что если сегодня будет такой же день, то я выгорю. Так что беру день отпуска от ботиков. Это было очень мудрое решение.

Конец первой части второго раунда. Моё место около 14. Есть 24 часа на правки. День отдыха дал о себе знать. Это было почти 24 часа программирования запоем. Пригодились мои “фундаментальные исследования” геометрии пуль, деталей прицеливания, разброса и т.п. Симуляция многих моментов, была сильно улучшены за счёт перехода на новую более тщательную и быструю модель мира. Остаётся 4 часа до запуска. Мозг уже заканчивается. В поисках, что бы ещё быстро и не сложно улучшить, перечитываю документацию. О! Есть мины. Я ими ещё не пользуюсь, т.е. они реализованы на 0%. Значит, возможно в них можно немного вложить и получить заметный рост. А есть проблема. Мой рейтинг побед около 90%. Стартовая стратегия работает по принципу: беги и “прилипай” вплотную к сопернику. Из-за особенностей карт держать дистанцию удаётся недолго, а вплотную уже неважно, насколько точно целиться и как уворачиваться. И мой условный шанс победы над стратегией, которая идет на сокращение дистанции, около 80%. Вроде хорошо, но это меньше моего текущего рейтинга побед. Простых стратегий довольно много. По правилам игры трюк поставить себе мину под ноги и взорваться вместе с врагом выгоден по очкам. Это кажется проще всего и надёжнее для защиты от любителей подойти вплотную. Пара строчек, пара ifов, мол если случайно всё совпало и есть мины, и враг уже рядом, и союзника рядом нет, то взрывайся нафиг, не испытывай судьбу. Конечно, программисту это было чуть скучнее и он рвался реализовывать хитрое чередование союзников по перезарядке оружия.

Общие улучшения были на пользу. Примерно 12 место второго раунда. Мины… пару раз помогли, пару раз из-за неточных условий наоборот, но в целом скорее положительный баланс.

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

Тут мне с мотивацией помогает уже достигнутое высокое место в раунде, обсуждения в чатике соревнования про CProfile и Cython (снижение сложности), и несколько друзей, которые свято уверены, что я просто очень умный и могу занять призовое место (немного повышение мотивации, немного повышение субъективного навыка).

Подготовка к финалу и финал. В финал я уже прошёл, значит надо в нём побеждать. Первые задачи тоже понятны. Поиск пути и оптимизация кода, иначе в финале делать нечего - юниты не найдут оружия или стратегия не уложится в лимит времени.

Пару слов про поиск пути. С первого же дня в чатике было много обсуждений про поиск пути, ругались страшными (для меня на тот момент) словами “дейкстра” и “астар”. Складывалось впечатление, что это что-то очень сложное и его надо начинать делать сильно заранее до последней недели. Мой программист пару раз тоже кричал, что раз это сложная задача, к которой вообще неясно что делать, то надо взяться за неё пораньше. Менеджер неизменно отвечал: “Пока отложим её. Пока забудь про неё. Я контролирую процесс”. Потому что субъективно это была задача сложнее чем навык и вызывала тревогу. К тому же было бы сложно получить явный результат, т.к. игр на сложных картах не проводилось. Итак, у меня 12 место в раунде. Большинство игроков из топового диапазона без особых проблем справляются с этой задачей. Вряд ли она кардинально сложнее всего, что я уже решил. Место и сравнение с другими сильно повысило субъективную оценку моих навыков и снизило сложность задачи. Она как раз оказалась в секторе потока. И вот именно тогда я взялся за поиск пути.

Оказалось, задача и правда куда проще, чем я думал. 2 часа - нагуглить и понять основные алгоритмы. И остаток дня - разработать и реализовать поиск пути для своей стратегии. И ещё 1,5 дня - написать навигатор, который сможет без особых багов водить по этому маршруту ботика. Из смешных моментов - мне помогло знакомство с навигаторами в смартфонах - часто бывает, что точка полученных GPS координат в одном месте, а стрелочка “вашего положения” в другом. Вот и мой навигатор действовал так же при сходе с маршрута. Если отклонение небольшое и незапланированное, то ещё пару мгновений будем считать, что это “ошибка позиционирования” и на самом деле юнит идёт по маршруту.

В итоге мой довольно простой поиск пути отлично работал.

А профилирование заставило меня долго ругаться. Я как раз в процессе рефакторинга переписал почти всё на предложенные организаторами типы данных, взятые из базовой модели. ООП, единообразие, наше всё. Огромный выигрыш в быстродействии я получил, переписав ещё раз все координаты на примитивный tuple.

Минимум к финалу - готов. Что дальше? Сейчас в песочнице проводятся бои по правилам обоих раундов и финала. Т.к. нас интересует только финал, то остальные игры сознательно игнорируем как не показательные. Так же не смотрим больше на рейтинг в песочнице, чтобы не делать универсального бота. Решение только под финал написать проще, чем универсальное. На картах финала больше аптечек и мин, и это играет роль: во-первых, мои ущербные мины начали приносить чуть больше пользы, во-вторых, в районе моего рейтинга образовалось много людей, которые побеждали за счёт стратегии “добежать до соперника и взорваться с ним”. В целом такая хорошо реализованная стратегия давала место что-то вроде 15-20 в общем зачёте. Я нашёл только один хороший вариант борьбы с ними: если они прибежали - взорваться первым. А если не прибежали, то расстреливать, т.к. стрельба и уворот у меня лучше реализованы. Потратив пару часов на анализ, пришлось увеличить приоритет действиям по сбору минимального комплекта мин, чаще держаться земли (в воздухе нельзя поставить мину, а пока я в прыжке, враг подбегал и взрывался со мной) - в целом повысить вероятность создания благоприятных условий для использования мины. Если не можешь сейчас взорвать мины, значит ты беззащитен против близкого врага. Это дало достаточную защиту и я радостно почти забыл про мины, оставив сам подрыв кривой проверкой после всех тщательно рассчитанных действий мол “а не выгодно ли взорваться ли нам сейчас?” Почему я не реализовывал стратегию “подбегаем к врагу для подрыва”? Я ошибся в предсказании действий других топов. Из-за простоты моей проверки я думал, что все её или лучшую воткнут как мастхэв и мины станут практически не применяемым оружием. Все юниты будут просто держаться друг от друга вне зоны действия мин, т.к. как только подойдёшь ближе, то тебя взорвут. Поэтому я радостно занялся более интересными частями алгоритма про командную работу и стрельбу. Как оказалось я ошибся и мины очень неплохо себя показали. А вот не надо подходить к мои юнитам - они от этого нервничают.

10 минут до старта финала, уже всё отправлено. Формально правки для себя запрещены, чтобы хуже не сделать. И тут вижу, что в одном месте вроде не учитывается какой-то момент. Сейчас улучшу! - Но… мы же не успеем оттестировать! - Да тут просто! Изменяю. Отсылаю. Код принят. И тут я смотрю на код ещё раз… я ошибся, и эти правки сломали проверку мин и иногда боты взрывались сами просто так :) Гонг - старт финала, на 12 часов новые стратегии не принимаются. Конечно, я исправил тут же обратно и отослал, но всю первую часть финала содрогался от периодического самоубийства своих ботов. Хорошо хоть не частого.

В итоге мои боты заняли четвёртое место не потому что у них было что-то одно очень хорошо реализовано, а из-за хорошего баланса навыков. У них была средняя стрельба, хорошие увороты, средние мины, хороший поиск пути и средняя командная работа. У участников ниже по рейтингу встречались лучше у кого стрельба, у кого увороты. У чистых минеров были офигенные мины, но плохая стрельба и увороты.

Из смешного про работу с мотивацией.

Перед вторым раундом я сильно улучшил алгоритм стрельбы. Учёт вероятности попадания, изменения разброса, наилучшая точка противника для усложнения уворота. И всё такое. Звучит очень всё хорошо. Тесты не показали выигрыша, а скорее небольшое падение процента попаданий. Программист отказался принимать такие результаты тестов - ещё пару раз проверил - должно быть сильно лучше. Менеджер, прикинув запас прочности стратегии и временя поиск проблемы, помечая в блокнотике: хорошо, хорошо, давай оставим. Тесты в 5-10 запусков с текущим рандомом и правда не показательны.

Приближается финал.

М: Слушай, я помню там были неоднозначны тесты новой системы прицеливания. Давай попробуем протестировать с более простой.

П: Давай.

Тестирую - лучше с простой.

Оба: ну и фиг с ней, отключаем.

Потому что прошло время и П уже это не так ценно. Для него сейчас гордость - поиск пути.

Итого:

Для реализации сложных и долгих штук нужно иметь запас по времени и мотивации, чтобы не бросить. Если его нет, то лучше делать вначале простые для накопления запаса. Даже если потом придётся переписать часть.
Очевидно, что работать в потоке эффективнее, но надо не забывать отдыхать.
Выбор тех задач, где можно получить максимальный выигрыш за затраченное времени.
Стремится решить поставленную задачу достаточно, а не абстрактно идеально. Проблема та же - время.
Гибкость. Готовность изменяться и принимать мир как он есть, а не как его хочется видеть. Приоритетные оружия у меня менялись раз 6, в зависимости от текущего уровня стратегий врагов и крутости моей стратегии. Если долго отрицать реальность и бухтеть на её несправедливость, то можно не успеть адаптироваться, как у многих случилось с минами.
Думает человек, работает компьютер. Во всяком случае я пока не могу заставить компьютер думать лучше меня, но он куда лучше работает. Зачастую час анализа заменяет 12 часов программирования - можно упростить задачу или вообще её не решать. Я был очень удивлён, когда в чате сказал, что если противник падает, то мы можем довольно точно предсказать его следующие позиции по высоте (очевидно ниже, т.к. прыгнуть или зависнуть невозможно), а мне сказали, что это толстая помощь другим. При том что ссылки на алгоритмы и прочее не являлись толстой помощью.

Благодарности

Mail.ru Group за интересный чемпионат в таком формате.
Alexander N за волшебную фразу “cProfile же, стандартный для питона, не самый удобный кстати”, упоминание Cython и моральную поддержку по возможности Python выйти в топ против уверенности основной части сообщества, что у Python без шансов.
Сообществу за тёплую атмосферу дружеского соперничества в чатике.
Всем участникам за интересные вызовы.
Друзьям, что в меня верили и поддерживали.
Lama, за видео.

Сейчас начался RAIC этого года! Если вы сомневаетесь, то присоединяйтесь - топовые места ждут вас.

Let's block ads! (Why?)

На американском сегменте МКС частично отказала система электропитания, отключены часть потребителей

Астронавты НАСА Боб Бенкен и Крис Кэссиди работают с внешними элементами МКС во время выхода в открытый космос. Источник фото: НАСА.

По информации агентства «РИА Новости», 12 декабря 2020 года на американском сегменте МКС произошла нештатная ситуация в системе электропитания. Специалисты ЦУП НАСА зафиксировали, что отключился один из блоков разрядки-зарядки аккумуляторных батарей, который находится снаружи станции. Данный элемент подключен к ферме с восемью панелями солнечных батарей, которые генерируют электричество для нескольких каналов электропитания бортовых систем МКС.
Из-за отказа этого модуля на треть уменьшилась подача электричества в одном из каналов для американского сегмента станции. Астронавтам пришлось отключить часть потребителей, чтобы стабилизировать ситуацию. В настоящее время в американском модуле Unity обесточены датчики дыма и бортовой компьютер, выключен блок высокоскоростной связи с Землей и один из четырех гироскопов, поддерживающих ориентацию МКС в пространстве.

Ситуация с проблемами в электропитании американского сегмента станции сейчас находится под контролем специалистов НАСА.

Примечательно, что в это же время на российском сегменте МКС также были зафиксированы неполадки. Снова отказала системы подачи кислорода «Электрон-ВМ», которая установлена в модуле «Звезда». Некоторое время космонавты своими силами пытались устранить неисправность. Они рассказали, что «Электрон-ВМ» отключился не из-за проблем с электропитанием, а из-за низкого давления кислорода в системе. Хотя поломка по времени совпала с отключением пылесоса, который космонавты использовали для уборки на российском сегменте МКС.

Наземные специалисты Роскосмоса, отвечающие за бортовые системы российского сегмента МКС уточнили, что им требуется дополнительное время для анализа причин отключения «Электрон-ВМ». Сейчас этот блок опять в разобранном состоянии, а космонавты ждут указаний из ЦУП для его ремонта.

Причем только 10 декабря система «Электрон-ВМ» была приведена космонавтами в рабочее состояния после предыдущей поломки. Только за последние два месяца эта система выходила из строя пять раз — 14, 17, 19 и 21 октября, а теперь 12 декабря. В Роскосмосе ранее поясняли, что эта поломка не угрожает жизни и здоровью экипажа МКС, а во время ремонта «Электрон-ВМ» продолжает работать дублирующая система в американском сегменте станции.

В настоящее время на МКС находятся российские космонавты Сергей Рыжиков и Сергей Кудь-Сверчков, американские астронавты Майкл Хопкинс, Виктор Гловер, Шэннон Уолкер и Кэтлин Рубинс, а также японский астронавт Соити Ногути.

Текущая конфигурация МКС.

См. также:

Let's block ads! (Why?)

Постквантовая криптография. Обзор протокола выработки ключей NewHope

Доброго времени суток!

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

Сегодня рассмотрим протокол NewHope, в основе которого лежит другая сложная задача - задача обучения с ошибками в кольце (Ring-LWE).

Протокол NewHope – это протокол совместной выработки ключа, который был разработан специально, чтобы противостоять атакам с помощью квантовых компьютеров. Прежде чем переходить непосредственно к алгоритму работы, рассмотрим задачи SIS, LWE и Ring-LWE:

1. SIS как задача на решётках

SIS (Short integer solution problem) – задача поиска короткого вектора на решётке в окрестности точки.

Имеется матрица А, столбцы которой состоят из целочисленных векторов длины n по модулю q (вектора выбираются случайно):

$A = (\overrightarrow{a_1}, \overrightarrow{a_2}, \dots, \overrightarrow{a_m}) \in \mathbb {Z}^{n \times m}_q$

Также введем символ $L^{\perp}$ или же ортогональную решётку от A:

$L^{\perp}(A) = \{ z \in \mathbb {Z}^m : Az = 0\}$

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

Задача состоит в том, чтобы при заданной матрице А найти ненулевой вектор $x \in \mathbb{Z}^m$ решётке такой, что Ax=0 . Задача решается методом Гаусса и, отчасти, ничего сложного в ней нет.

Введем параметр $\beta \ll q$ и поставим условие, что мы ищем достаточно короткий вектор z, такой что $||z|| \leq \beta \ll q$ . Это условие должно выполняться для любого положительного вектора z (они целочисленные по модулю q). Аналогично задачу можно перефразировать так, что мы ищем вектор, принадлежащий окрестности точки решётки. Так как мы матрицу А выбирали случайным образом, то мы поставили задачу в общем случае.

Как можно усложнить задачу? Сдвинем решётку на небольшое расстояние, это привнесет в нее шум (главное не сдвигать слишком сильно).

Предлагается выбирать сдвиг $t \ll T$ - периода решётки. Иначе возникнет проблема с восстановлением вектора z.

$L_u^{\perp}(A) = \{z: Az=u\} = t + L^{\perp}(A)$

Теперь после внесения шума, искать короткий вектор z по заданному A становится очень сложной задачей.

Если мы работаем в евклидовой норме, то можем получить асимптотическую сложность в $2^{\theta(n)}$ , где n - размерность пространства.

2. LWE ( Learning with errors)

Рассмотрим задачу обучения с ошибками:

Параметры задачи:

n – размерность пространства;

q – число, как и в прошлой задаче. Здесь оно берется с полиномиальной зависимостью от n, порядка $q \approx n^2$ ;

А также функция распределения ошибок $\chi$ берется нормальное распределение, для красивых формул в доказательствах);

Как и в прошлой задаче зададим случайную матрицу $A \in \mathbb{Z}^{n \times m}_q$ столбцы которой вектора $a_i \in \mathbb{Z}^n_q$ ;

И вектор k, который будет отвечать за шум из распределения $\chi$ .

Задача состоит в том, что злоумышленнику необходимо найти секретный вектор $s \in \mathbb{Z}^n_q$ , когда ему известны всевозможные зашумленные скалярные произведения s с векторами a_i . (Все операции выполняются по модулю q):

$a_1 \gets \mathbb{Z}^n_q ,\: b_1 \approx\: <s, a_1> \: mod \: q$ $a_2 \gets \mathbb{Z}^n_q ,\: b_2 \approx\: <s, a_2> \: mod \: q$ $\dots$

Или точнее

$b_1=<s,a_1>+k_1\in \mathbb{Z}_q$

Где k_1 первая компонента вектора .

Однако нас интересует модификация задачи, так называемое обучение с ошибками на решётках (LWE on lattices).

Зададим решётку:

$L\left(A\right)=\{z\in \mathbb{Z}^m:z^T\equiv s^TA\ mod\ q\}=q\left(L^\bot\left(A\right)\right)$

Задача уже подменяется другой – декодирование с ограниченным расстоянием.

Задана решётка, и дана точка q. Необходимо в её окрестности найти ближайшую к ней точку решётки.

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

Дано: $b^T\approx v^T=s^TA\in L(A)\$ найти .

3. Примеры

Рассмотрим создание криптографической системы с открытым ключом на LWE, а также хеш-функцию на SIS:

Public key encryption (LWE):

Боб хочет отправить сообщение Алисе, зашифрованное с помощью её открытого ключа. Сообщение в данном примере – бит информации.

В данной схеме надо учесть, что разность ошибок $e^\prime-ex\ll\ \frac{q}{2}.$

Если получившаяся разность ближе к 0, то декодирован 0, и если к $\frac{q}{2}$ то 1.

Что у нас знает хакер? (A, u) и (b, b’) . Так как в них замешано умножение на случайную матрицу с примесью шума, то выходит, что на руках у него 4 случайных величины, с помощью которых узнать сообщение не выйдет.

One-way function (SIS):

Построение хеш-функции предлагается осуществлять по схеме Меркла-Дамгора:

Перерисовано с https://www.di.ens.fr/chloe.hebant/presentation/SISproblem.pdf — Перерисовано с https://ift.tt/2Lw9pRp

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

Дамгор и Меркл независимо показали, что если будет устойчивой к коллизиям, то и H(m) будет устойчива.

Наша задача построить функцию - устойчивую к коллизиям (One-way function):

Так же, как и ранее определим:

$n \in \mathbb{N}$ зафиксируем q = poly(n) и m = m(n) .

Определим H_n - семейство функций $\{f_A\}_{A\in Z^{n\times m}}$ такие что $f_A:\{0,1\}^m\rightarrow Z_n^m$

И для битового вектора $e\in{\{0,1\}}^n$ функция будет задаваться как:

$f_A\left(e\right)=A \times e\>\ mod\>\ q$

Определение довольно естественное в контексте задачи SIS.

Что насчет коллизий? Была доказана лемма, что сложность нахождения коллизии в указанной выше задачи с вероятностью аналогична сложности решения задачи SIS с той же вероятностью.

4. Проблемы с использованием этих задач в реальных криптосистемах

При использовании в реальных криптосистемах возникает ряд проблем:

Необходимость пересылки очень большого количества данных. На слайде приведена матрица для размерности $640 \times 8$ и ограничением 15 бит на число:

Источник: https://summerschool-croatia.cs.ru.nl/2018/ — Источник: https://ift.tt/3a3qts5

2) Все операции шифрования/дешифрования происходят с асимптотической сложностью O(n^2) , что довольно медленно.

Какое решение у этих проблем?

5. Ring-LWE

Обучение с ошибками в кольце решает сразу обе вышеописанные проблемы.

Какая идея была у создателей? Вспомним, что в LWE задаче мы имеем много разных скалярных произведений. Что если задать операцию скалярного произведения так, чтобы мы могли получить n псевдослучайных скаляров из одного?

$\left(\begin{matrix}\begin{matrix}\vdots\\a_i\\\end{matrix}\\\vdots\\\end{matrix}\right)\widetilde{\ast}\left(\begin{matrix}\begin{matrix}\vdots\\s\\\end{matrix}\\\vdots\\\end{matrix}\right)+\left(\begin{matrix}\begin{matrix}\vdots\\e_i\\\end{matrix}\\\vdots\\\end{matrix}\right)=\left(\begin{matrix}\begin{matrix}\vdots\\b_i\\\end{matrix}\\\vdots\\\end{matrix}\right)\in \mathbb{Z}_q^n$

Как определить операцию $\widetilde{\ast}$ ?

Наилучший способ – умножение в кольце многочленов R_q=R/qR , где $R = \mathbb{Z}_q\left[X\right]/\left(X^n+1\right)$ , n – степень двойки.

Элементы R_q имеют степень ${deg(R}_q)<n$ c коэффициентами по модулю q.

Почему именно такой способ? Необходимость передавать большие матрицы отпадает. В самом деле, достаточно передать один полином, остальные можно получить циклическим сдвигом по правилу: $x\ \rightarrow\ -x\ mod\ q$ . В итоге получаем достаточно случайную матрицу.

Что насчет шифрования/дешифрования? С помощью быстрого преобразования Фурье, можно получить перемножение 2 полиномов за $O\left(n\ logn\right)$ , что значительно быстрее $O\left(n^2\right).$

Задача получается аналогичной LWE за исключением того, что a_i, s, k уже являются полиномами, а не просто векторами.

6. Протокол NewHope

Если кратко говорить, то протокол NewHope является модификацией протокола обмена ключами, который описали в своей статье Bos, Castello, Naehrig и Stebila. Они реализовали обмен ключами в TLS из Ring-LWE.

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

В данной схеме я буду пользоваться обозначениями, введёнными авторами статьи.

Разберём стадии и функции подробнее:

Здесь Алиса является сервером, а Боб клиентом.

В качестве параметров системы n = 1024, q = 12289 (наименьшее простое, для которого $q\equiv1\ mod\ 2n$ ). Это необходимо для быстрой работы NTT (вариация дискретного преобразования Фурье для полиномов), который требует n – степени двойки, q – простое число, которое соответствует указанному выше требованию. Используется решётка
В начале необходимо сгенерировать случайный полином a. Происходит это так: генерируется seed – псевдослучайное число длиной 256 бит, далее это число пропускается через функцию SHAKE-128 (в работе авторов в качестве данной функции используется SHA3). Затем начинает работать парсер, который выберет 1024 коэффициента в полином a. Небольшая ремарка: несмотря на то, что TLS имеет кэширование ключей на некоторое время (в районе 2 часов), авторы протокола NewHope выступили против этого, и по умолчанию для каждого нового соединения генерируется свой полином a. По их мнению, это уменьшает шанс на backdoor и возникновения проблемы, что все соединения будут полагаться на единственный “экземпляр” задачи в решётках.
Функция распределение ошибок – биноминальное, центрированное. Это сделано из-за того, что моделировать нормальное распределение довольно затратно и не нужно хранить таблицы вычисленных значений (что исключает некоторые типы атак). Здесь использован псевдослучайный генератор с seed из /dev/urandom с последующим быстрым суммированием 16-битовых блоков вывода. Выборкой из нее получаем коэффициенты для секретного полинома s и полинома ошибок e.
Пересылается пара (открытый ключ b, seed).
На стороне клиента также генерируется полином a, полиномы s’, e’, e”, вычисляется открытый ключ u.
Дальше необходимо получить полином v, который должен быть одинаковым и для клиента, и для сервера. Однако с этим возникают трудности. На стороне клиента получается , на стороне сервера , в итоге накапливается погрешность между полиномами, которую необходимо исправить. Если помните, различение переданного бита – это то, насколько значение близко к 0 или $\frac{q}{2}$ . Соответственно, большая погрешность может привести к искажению сообщения.
Выполним коррекцию ошибки. Для начала вернемся от полиномов к векторам: коэффициенты полинома будут координатами вектора. Разделим их на q и таким образом, отобразим их на $\left[0,1\right)$ . Так как мы работаем в решётке то для примеров перейдем в (в четырёхмерном пространстве рисовать тяжело). Для начала немного изменим нашу решетку и перейдем к базису $\{ \left(0,\ 1\right),\left(1/2,\ 1/2\right) \}$ . На двумерной решётке нужно нарисовать диаграмму Вороного.

источник https://eprint.iacr.org/2015/1092.pdf — источник https://ift.tt/1kiMs0q

И наша задача отобразить вектор в бит информации однозначно. Допустим, что клиент и сервер имеют один и тот же вектор, тогда отображение вектора в бит информации довольно простое: если вектор попал в серую область ячейки Вороного, то он 1, если вне её, то 0. Однако все усложняется тем, что у клиента и сервера есть только зашумленные варианты векторов, так что можно получить разные значения. Для исправления этого вводится функция HelpRec, которая находит сдвиг до ближайшей точки решётки. Её необходимо выполнить на одной из сторон и результат переслать второй стороне. Важно то, что она сообщает сдвиг до ближайшей точки решётки, а не какой бит должен получиться.

8. Далее функция Rec ищет 1 бит ключа из 4 коэффициентов полинома (с учетом сдвига).

9. После хеширования получаем ключ длиной 256 бит, который будет одинаковым и у клиента, и у сервера.

7. Применение и стандартизация

Протокол был предложен в 2019 NIST post-quantum crypto project, прошел во второй раунд, но не прошел в третий раунд. В отчете NIST говорится, что благодаря своей структуре протокол имеет очень высокую производительность, однако он не превзошел своего конкурента KYBER (который основан на задаче Module-LWE) по безопасности, а также проиграл ему в ряде бенчмарков. В итоге в 3 раунд прошел протокол KYBER.

Также, протокол тестировал Google в проекте Canary вместе со своим CECPQ1 и CECPQ2.

Источник: https://security.googleblog.com/2016/07/experimenting-with-post-quantum.html — Источник: https://ift.tt/29pI6Tl

Реализации протокола:

Источники:

Let's block ads! (Why?)

...

суббота, 12 декабря 2020 г.

Чтобы на фотографиях на аттракционах никто не снимал маски, в парках «Диснейленда» их добавят цифровым способом

Разработка симулятора космического корабля Союз ТМА

Программисты разгадали очередной шифр убийцы Зодиака спустя полвека

Russian AI Cup 2019. 4 место, почти не умея программировать или о пользе soft skills

О чемпионате

Какие нужны навыки?

Платформа

Немного теории о “потоке” и модели Фогга в моём кратком изложении.

Программист VS менеджер

История участия

Итого:

Благодарности

На американском сегменте МКС частично отказала система электропитания, отключены часть потребителей

Постквантовая криптография. Обзор протокола выработки ключей NewHope

1. SIS как задача на решётках

2. LWE ( Learning with errors)

3. Примеры

4. Проблемы с использованием этих задач в реальных криптосистемах

5. Ring-LWE

6. Протокол NewHope

7. Применение и стандартизация

суббота, 12 декабря 2020 г.