Использование модулярной арифметики в алгоритме гомоморфного шифрования Выполнила: Чечулина Дарья Научный руководитель: Кренделев С. Ф. Лаборатория современных компьютерных технологий НИЧ НГУ

Определение Модулярная арифметика (или арифметика остатков) – метод выполнения арифметических действий над большими целыми числами, основная идея которого состоит в том, чтобы оперировать не непосредственно числом u, а его «остатками» по различным модулям m 1 …m r (причем все модули взаимно просты) 2

Обозначения u, v – большие целые числа m 1,…,m r – модули, не содержащие общих делителей u 1 = u mod m 1, …, u r = u mod m r v 1 = v mod m 1, …, v r = v mod m r (u 1, …, u r ), (v 1, …, v r ) – модулярное представление чисел u и v m = m 1 ×…×m r – область чисел, над которыми можно выполнять все операции 3

Арифметические операции Сложение (u 1, …, u r ) + (v 1, …, v r ) = ((u 1 + v 1 ) mod m 1, …, (u r + v r ) mod m r ) Вычитание (u 1, …, u r ) - (v 1, …, v r ) = ((u 1 - v 1 ) mod m 1, …, (u r - v r ) mod m r ) Умножение (u 1, …, u r ) × (v 1, …, v r ) = ((u 1 × v 1 ) mod m 1, …, (u r × v r ) mod m r ) 4

Китайская теорема об остатках Пусть m 1,…,m r – положительные целые попарно простые числа, т.е НОД (m j, m k ) = 1, j k Пусть m = m 1 × m 2 × … × m r и пусть также a, u 1, …, u r – целые числа. Тогда существует ровно одно целое число u, удовлетворяющее условиям a u < a + m, u = u j (mod m j ), 1 j r 5

Пример 1. Прямая задача u = 73, v = 12 u × v = 876 r = 3 – количество используемых «модулей» m 1 = 11, m 2 = 7, m 3 = 13 – взаимно простые «модули» m = m 1 × m 2 × m 3 = 1001 u 1 = u mod m 1 = 7, u 2 = 3, u 3 = 8 v 1 = v mod m 1 = 1, v 2 = 5, v 3 = 12 (u 1, u 2, u 3 ) × (v 1, v 2, v 3 ) = ((7 × 1) mod 11, (3 × 5) mod 7, (8 × 12) mod 13) = (7, 1, 5) 6

Пример 2. Обратная задача (u 1, u 2, u 3 ) × (v 1, v 2, v 3 ) = (w 1, w 2, w 3 ) = (7, 1, 5) u × v - ? Пользуясь т. Эйлера, найдем: M j = (m / m j ) φ(m j ) mod m где φ(m j ) = (m j – 1) – функция Эйлера для простых чисел m j M 1 = (7 × 13) 10 = 364, M 2 = (11 × 13) 6 = 715, M 3 = (11 × 7) 12 = 924 M j = 1 mod m j, M j = 0 mod m k, k j u × v = (w 1 × M 1 + w 2 × M 2 + w 3 × M 3 ) mod m = = (7 × × × 924) mod m = ( ) mod m = 1877 mod m = 876 7

Недостатки алгоритма гомоморфного шифрования с использованием только длинной арифметики Большие объемы данных, получаемые при выполнении арифметических операций над длинными целыми числами Большая длина шифротекста на выходе алгоритма шифрования 8

Преимущества использования модулярной арифметики Возможность параллельного выполнения операций повышение производительности алгоритма Повышение стойкости алгоритма к криптоаналитическим атакам Уменьшение объема выходных данных при умножении длинных целых чисел Сокращение длины шифротекста 9