Гомоморфное шифрование своими руками

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

    Гомоморфное шифрование — криптографическая система, которая позволяет проводить определенные математические действия с открытым текстом путем произведения операций с зашифрованным текстом.

    Долгое время полностью гомоморфная криптосистема оставалась для всех криптографов мира священным Граалем, недостижимым идеалом. И вот в 2009 году Craig Gentry в своей диссертации впервые описал полностью рабочую схему гомоморфного шифрования.
    Несколько математических подробностей идеи Gentry а также пример реализации его алгоритма вы найдете под катом.

    Гомоморфное шифрование.


    Любую стандартную систему шифрования можно описать тремя алгоритмами.
    • Генерация ключей KeyGen()
    • Шифрование Encypt()
    • Расшифровка Decrypt()

    Гомоморфная криптосистема помимо трех вышеперечисленных алгоритмов включает в себя алгоритм вычислений Eval().
    Схематично алгоритм Eval можно представить следующим образом:

    На вход алгоритму подается зашифрованное сообщение Enc(M) и некая математическая функция f(). Результатом работы алгоритма является другое зашифрованное сообщение Enc(M2), причем M2=f(M).

    Схема гомоморфного шифрования считается корректной если для любой пары ключей SK, PK, для любой функции f(), для любого набора шифротекстов С={c1,c2,..,cn} и набора открытых текстов M={m1,m2,..,mn} , таких что C=Enc(M) выполняется следующее условие:
    Если r=Eval(PK,C,f) тогда decypt(SK,r)=f(m1,m2,..,mn)
    Схема предложенная Gentry соответствует данному условию и поэтому ее можно назвать полностью гомоморфной.

    Схема Gentry с числами


    Опишем саму схему шифрования применимую для данных представленных в числовом виде.
    KeyGen
    Закрытый ключ: большое четное число N.
    Открытый ключ: набор больших чисел {a1,a2,..,ai} таких что ai mod N=2ei, где ei числа намного меньше N.
    Encrypt
    Из открытого ключа генерируем случайное число b=random-subset-sum{ai}. Для того чтобы зашифровать 1 бит информации m ∈{0,1} вычислим
    С=b+m
    Decrypt
    Для расшифровки вычислим
    С mod N=m+2*Пei
    2*Пei называют шумом, если данное выражение в процессе вычислений станет больше числа N, то расшифровка будет невозможна.
    После приведения по модулю два получим исходное сообщение m.
    Eval
    Чтобы произвести сложение или умножение зашифрованных элементов не расшифровывая их, достаточно просто сложить или умножить шифротексты.
    Несмотря на то что эта схема является абсолютно рабочей, она представляет не очень большой интерес, т.к. с ее помощью можно зашифровать только 1 бит информации. Для того чтобы работать с большими числами немного видоизменим алгоритм.
    Построим схему, которая бы позволяла нам шифровать числа не больше 15.
    KeyGen
    Закрытый ключ: большое число N, такое что НОД(N,15)=1.
    Открытый ключ: набор больших чисел {a1,a2,..,ai} таких что ai mod N=15ei, где ei числа намного меньше N.
    Encrypt
    Из открытого ключа генерируем случайное число b=random-subset-sum{ai}. Для того чтобы зашифровать число от 0 до 15 вычислим
    С=b+m
    Decrypt
    Для расшифровки вычислим
    С mod N=m+15*Пei
    После приведения по модулю 15 получим исходное сообщение m.

    Реализация на C#


    Ниже приведена часть кода, содержащая функции генерации ключей, шифрования и дешифрования.
            //функция генерации ключей, переменная k-максимальное значение числа 
            //с которым может работать криптосистема
            private BigInteger[] PublicKeyGenerate(BigInteger N, int k)
            {
                Random r = new Random();
                byte[] rand = new byte[16];
                BigInteger rem;
                for (int i = 0; i < 100; i++)
                {
                        r.NextBytes(rand);
                        PK[i] = new BigInteger(rand);
                        PK[i] = (BigInteger.Abs(PK[i]) * N) + (k* r.Next(10, 100));
                        rem = BigInteger.Remainder(PK[i], N);;
                }
                return PK;
            }
            //функция шифрования, параметрами служат
            // открытый текст M и Открытый ключ PK
            private BigInteger Encryption(BigInteger M, BigInteger[] PK)
            {
                BigInteger B = new BigInteger(0);
                BigInteger C = new BigInteger(0);
                Random r = new Random();
                for (int i = 0; i < 100; i++)
                {
                    if (r.Next(2) == 1)
                        B = B + PK[i];
                }
                C = M + B;
                return C;
            }
            //функция дешифровки, C-шифротекст, N-закрытый ключ, 
            //k-максимально допустимое значение открытого текста
            private BigInteger Decryption(BigInteger C, BigInteger N, int k)
            {
                BigInteger M = new BigInteger(0);
                M = BigInteger.Remainder(C, N);
                return BigInteger.Remainder(M, k);
            }
    

    Скачать исходники программки реализующей шифрование чисел до 1000 можно отсюда.

    Заключение


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

    Ссылки на источники


    AdBlock has stolen the banner, but banners are not teeth — they will be back

    More
    Ads

    Comments 34

      +4
      Интересно. Скажите, а практическое применение этому какое?
        +5
        Подпись платежей без раскрытия суммы.
          +1
          Изменение суммы платежа без раскрытия подписи? :)

          Вижу два интересных направления на поиск уязвимости:
          * Man in the Middle
          * Выполнение операций над исходным сообщением для приведения его в состоянее, позволяющее быстро вычислить ключ.

          Похоже, всю эту гомоморфную крипту придется все равно подписывать старой доброй ЭЦП.
          +10
          Конкретно этой схемы никакого:)
          А если говорить вообще о гомоморфном шифровании, то оно открывает большие возможности для облачных вычислений. Ведь используя такой способ шифрования, вы сможете отправить данные в облако в зашифрованном виде. И чтобы обработать эти данные и вернуть результат вычислений облаку даже не нужно будет знать ваш секретный ключ, т.е. никто кроме вас даже теоретически не сможет получить доступ к вашим секретным данным, хотя при этом вы сможете пользоваться всеми прелестями облачных технологий.
            +1
            Я правильно понимаю, что мы можем изменить сообщение не зная секретного ключа?
              0
              Функция E гомоморфна относительно операции op над открытыми текстами, если существует эффективный алгоритм M, который получив на вход любую пару криптограмм вида E(k, m1), E(k, m2), выдает криптограмму c такую, что при дешифрировании c будет получен открытый текст m1 op m2.
                0
                Да.
                Есть книга Malicious Cryptography, где в качестве примера указывали применение для автора вируса:
                Каждый экземпляр перед размножением увеличивает счётчик на единицу и только автор потом может анализировать результаты.
                  0
                  А что там за алгоритм шифрования использовался? RSA?
              0
              Например, некий «dropbox» хранит ваши данные зашифрованные вашим ключем (т.е. сам прочитать их не может), а нечто вроде полнотекстовой индексации по ним делать может.
                +1
                Как он сделает индексацию если исходные данные недоступны?
                  0
                  Будет искать в зашифрованных данных заданные ключевые слова. В терминах статьи, f_W(M) = if (M contains W) then 1 else 0;.
                    0
                    Кхм, простите, у меня какой-то когнитивный диссонанс. Каким это образом третья сторона будет что-то искать в зашифрованных данных?
                      0
                      Наверное он хочет сказать, что третья сторона сделает индексацию обработку внутри самого контейнера.
                      При этом данные прочесть так и не сможет
                        +1
                        Как-то это все неубедительно звучит…
                        +1
                        Рассмотрим утрированный вариант: шифрование осуществляется XOR-ом каждого байта сообщения с однобайтовым ключом K, известным только клиенту. Сервер хранит зашифрованные данные. «Индексируем» однобайтовые «ключевые слова». Каждому такому ключевому байту W, соответствует функция f_W(M) = if (M contains W) then 1 else 0, которая ищет ключевой байт в clear-text. Ей соответствует функция Enc(f_W), которая ищет ключевой байт W в зашифрованном тексте. В нашем случае Enc(f_W) можно выписать явно: Enc(f_W)(S) = if (S contains (W XOR K)) then 1 else 0 (где S зашифрованный текст).

                        Для индексации, клиент передает серверу список ключевых слов и соответствующих функций: ((W XOR K), Enc(f_W)), ((Y XOR K), Enc(f_Y)), ...). Сервер запускает функции и строит индекс, не зная ключа. Понятно, что вместо передачи собственно функций их можно как-то параметризовать и передавать параметр. В нашем случае, никакого параметра вообще не требуется: (W XOR K) однозначно определяет функцию поиска в зашифрованном тескте.

                        В общем случае, метод остается тем же: ключевому слову сопоставляется функция поиска, ей сопоставляется функция поиска в зашифрованном тексте. То, что это будет именно функция поиска (а не расшифровка с последующим поиском в clear-text), гарантируется гомоморфностью алгоритма шифрования.
                          +1
                          Тут понимаете какое ограничение есть. Схема то гомоморфна относительно двух операций: умножения и сложения. Полностью гомоморфной ее называют из-за того что с помощью этих двух операций можно выразить любую другую математическую операцию. Т.е. если вашу функцию F_W() можно будет описать только с помощью умножения и сложение, то тогда да, то о чем вы говорите будет возможно.
                            0
                            Причем, например, для RSA мы ограничены только умножением.
                              0
                              Если я не путаю, умножение и сложение не является базисом без отрицания.
                              Так что любую функцию выразить не получится
                                +2
                                Полностью гомоморфное шифронание (fully homomorphic encryption), описанное Craig Gentry, гомоморфно относительно цепей (circuits), составленных из NAND, в которых можно выразить любую операцию. См. ссылку на его диссертацию выше.
                                  0
                                  Да вы правы, я совсем упустил что в основной работе речь шла о логических операциях.
                          +5
                          Пример. Один парень разработал алгоритм, позволяющий оценить параметры бизнес-плана. Второй парень разработал отличный бизнес-план. Первый не хочет делиться алгоритмом, второй волнуется, что у него украдут данные.

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

                          Проще говоря, гомоморфное шифрование позволяет оперировать зашифрованными данными, не зная их содержания.

                          По-моему, это очень клёво.
                            –1
                            Да уж… это очень клёво когда можно модифицировать подписанные данные, при сохранении их валидности.
                              +1
                              Ну что за скепсис. Мы же не говорим, что обычные схемы ЭЦП с появлением гомоморфных алгоритмов сразу вымрут. Вполне мирно могут сосуществовать и те и другие. Просто будут применяться для разных целей.
                                0
                                речь идёт о шифровании, а не о ЭЦП,
                                  0
                                  У меня для вас плохие новости…
                                    0
                                    С таким ником только такие комментарии и писать :-)
                                      0
                                      а у меня — для вас…
                                0
                                — электронное голосование
                                — проверка целостности данных
                                — разграничение доступа (совмесный доступ без раскрытия)

                                возможных прменений много… проблема только в том, что текущие реализации далеки от совершенства
                                0
                                С теоретической точки зрения гомоморфное шифрование — это круто, просто нирвана для криптографа, то, о чем они мечтают уже три десятка лет. Но с практической — это бич криптографии, и то, с чем предстоит еще очень много работы.
                                  0
                                  Только вот вычислительная сложность при работе с зашифрованным сообщением значительно выше, чем сложность при работе с исходным, или я неправильно понял статью?
                                    0
                                    Ну это да, и это кстати одна из причин почему гомоморфное шифрование еще нигде не применяется. Очень много вычислительных можностей надо чтобы работать над шифротекстами.
                                    +1
                                    Так как с темой гомоморфного шифрования я знаком не понаслышке, добавлю немного информации по теме.

                                    Схема шифрования, представленная в этом посте на самом деле не является честным гомоморфным шифрованием, так как не порождает гомоморфизма в математическом понимании этого термина. Это легко понять, взглянув на наличие ограниченное количество операций до того как шифротекст потеряет возможность расшифровки в силу роста шума, о чем автор поста справедливо упомянул. По этой причине Гентри назвал эту схему Somewhat Homomorphic Encryption.

                                    На самом деле истинная заслуга Гентри в том, что он на основе этой схемы сумел построить настоящее гомоморфное шифрование без ограничения числа операций, применив процедуру, названную им Bootstrapping. Единственное, почему данная схема не применяется на практике — она очень требовательна к ресурсам процессора и памяти. Но принципиальное существование грааля криптографии он доказал, за что ему честь и хвала.

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

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

                                    В основе лежит очень простая идея. Пусть мы хотим защифровать числа a и b. Тогда мы берем и строим полиномы A(x) и B(x) такие, чтобы числа a и b были их свободными членами. Фокус первый: если перемножить или сложить эти полиномы, в свободном члене результата окажутся числа a*b и a+b соответственно. Фокус второй: надо построить секретный полином P(x) такой, чтобы он задавал обратимую замену переменных, тогда шифрование будет осуществляться подстановкой замены переменных: A'(x)=A(P(x)) и B'(x)=B(P(x)). Расшифрование — подстановкой обратной замены переменных, т.е. A(x)=A(P(Q(x))), где Q(x) — как раз полином обратной замены. Нетрудно доказать, что выполненные над зашифрованными полиномами операции сложения и умножения будут операциями гомоморфного шифрования.

                                    Я отдаю себе отчет, что из этого сжатого изложения непросто понять, как это работает, и, тем более, почему. Поэтому даю ссылку на более аккуратное изложение этой информации — тезисы моего доклада на Positive Hack Days от сего года и на презентацию от него же.

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

                                    Если тема интересна, могу написать отдельный пост по данным схемам шифрования — материала у меня навалом :-)
                                      0
                                      Спасибо за такой интересный комментарий. Да я понимаю что описанная в топике схема всего лишь Somewhat Homomorphic Encryption, просто честно говоря отсутсвие времени да и слабое знания английского языка не позволили рассмотреть чтоже скрывается под этой идеей, в частности что такое Bootstrapping и как она работает.
                                      Поэтому лично мне ваш пост было бы вдвойне интересно почитать. Просим, просим.:)

                                    Only users with full accounts can post comments. Log in, please.