Криптосистема Блюма — Гольдвассер

Криптосистема Блюма — Гольдвассер — одна из схем шифрования с открытым ключом, основанная на сложности факторизации больших целых чисел. Этот алгоритм шифрования был предложен Мануэлем Блюмом и Шафи Гольдвассер в 1984 году.

Пусть m1, m2, … , mm — последовательность бит открытого текста. В качестве параметров криптосистемы выбираем n=pq — число Блюма, x0 — случайное число из Zn, взаимно простое с N.

В качестве открытого ключа для шифрования выступает n, в качестве секретного ключа для расшифрования — пара (p, q).

Для того, чтобы зашифровать открытый текст, обладатель открытого ключа выбирает x0. На основе BBS-генератора по вектору инициализации x0 получают последовательность квадратов x1, x2, … , xm, по которой получают последовательность младших бит b1, b2, …, bm. Путём гаммирования с этой последовательностью битов открытого текста и получают шифрованный текст ci=mi⊕bi, i=1,2,…,m.

Шифрограмма, которая пересылается обладателю секретного ключа, есть (c1,c2,…,cm, xm+1). После формирования шифрограммы последовательность xi, i=0,1,…,m уничтожается, и при следующем сеансе связи отправитель выбирает новое x0.

Получатель шифрограммы восстанавливает по xm+1 последовательность главных корней xm, … , x1 и последовательность их младших бит b1, b2, …, bm, а затем расшифровывает шифрограмму: mi=ci⊕bi , i=1,2,…,m.

Как происходит шифрование сообщений

Предположим, что Боб хочет послать сообщение «m» Алисе:

  1. Боб сначала кодирует в виде строки из бит
  2. Боб выбирает случайный элемент , где , и вычисляет
  3. Боб использует псевдослучайные числа для генерации случайных чисел , следующим образом:
    1. Для до :
    2. Ряд равен наименьшему значению бита ;
    3. Увеличиваем  ;
    4. Вычисляем
  4. Вычисляем зашифрованный текст с помощью гамирования ключевого потока
  5. Боб отправляет зашифрованный текст

Как происходит расшифрование сообщений

Алиса получает . Она может восстановить «m», используя следующую процедуру:

  1. Используя разложение на множители Алиса получает и .
  2. Вычисление начального источника
  3. Начиная с , повторно вычисляем битовый вектор используя генератор BBS, как в алгоритм шифрования.
  4. Вычисляем текст с помощью гаммирования ключевым потоком с зашифрованным текстом .

Алиса восстановила исходный текст

Эффективность

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

Примечания

Ссылки

  • M. Blum, S. Goldwasser, «An Efficient Probabilistic Public Key Encryption Scheme which Hides All Partial Information», Proceedings of Advances in Cryptology — CRYPTO '84, pp. 289—299, Springer Verlag, 1985.
  • Menezes, Alfred; van Oorschot, Paul C.; and Vanstone, Scott A. Handbook of Applied Cryptography. CRC Press, October 1996. ISBN 0-8493-8523-7

Read other articles:

Linux Foundation open-source project This article needs additional citations for verification. Please help improve this article by adding citations to reliable sources. Unsourced material may be challenged and removed.Find sources: Yocto Project – news · newspapers · books · scholar · JSTOR (April 2016) (Learn how and when to remove this template message) Initial release2010; 14 years ago (2010)Stable release4.3 (Nanbield) / October&#...

 

La rationalité limitée (bounded rationality en version originale) est l'idée selon laquelle la capacité de décision d'un individu est altérée par un ensemble de contraintes comme le manque d'information, des biais cognitifs ou encore le manque de temps. Dans cette optique, les décideurs ont tendance à choisir des solutions satisfaisantes plutôt qu'optimales. Le concept a été initialement théorisé par Herbert Simon et utilisé en sociologie, en psychologie, en microéconomie ou e...

 

Синелобый амазон Научная классификация Домен:ЭукариотыЦарство:ЖивотныеПодцарство:ЭуметазоиБез ранга:Двусторонне-симметричныеБез ранга:ВторичноротыеТип:ХордовыеПодтип:ПозвоночныеИнфратип:ЧелюстноротыеНадкласс:ЧетвероногиеКлада:АмниотыКлада:ЗавропсидыКласс:Пт�...

2008 single by DJ Felli Fel featuring Kanye West, Jermaine Dupri, Fabolous and Ne-YoFiner ThingsSingle by DJ Felli Fel featuring Kanye West, Jermaine Dupri, Fabolous and Ne-YoReleasedMarch 11, 2008Recorded2007–2008GenreHip hopLength4:14LabelSo So DefIDJMGSongwriter(s)James Andrew Corrine Jermaine Dupri John David Jackson Shaffer Chimere Smith Kanye West[1] Producer(s)DJ Felli FelDJ Felli Fel singles chronology Get Buck in Here (2007) Finer Things (2008) Feel It (2009) Kanye West...

 

1995 television film This article is about the original footage. For the 2006 feature film based on events surrounding it, see Alien Autopsy (2006 film). VHS cover of Alien Autopsy: Fact or Fiction Alien Autopsy: Fact or Fiction is a 1995 pseudo-documentary containing grainy black and white footage of a hoaxed alien autopsy.[1][2] In 1995, film purporting to show an alien autopsy conducted shortly after the Roswell incident was released by British entrepreneur Ray Santilli. ...

 

Multi-use stadium in Pelotas, Brazil Estádio Bento Mendes de FreitasSisbrace Full nameEstádio Bento Mendes de FreitasLocationPelotas, Rio Grande do Sul, BrazilOwnerGrêmio Esportivo BrasilCapacity18,000[1]SurfaceGrassOpenedMay 23, 1943TenantsGrêmio Esportivo Brasil Estádio Bento Mendes de Freitas is a multi-use stadium located in Pelotas, Brazil. It is used mostly for football matches and hosts the home matches of Grêmio Esportivo Brasil. The stadium has a maximum capacity of 18,...

Untuk kegunaan lain, lihat Barney dan Barney. Barney & FriendsLogo Barney & FriendsPembuatSheryl Leach[1]PemeranDavid Joyner (2001)Carey Stinson (2009)Josh Martin (2002; sut Barney)Bob West (2001)Duncan Brannan (2002)Tim Dever (2002)Dean Wendt (2009; suara Barney)Jenny Dempsey (1992)Jeff Ayers (2009; sut Baby Bop)Julie Johnson (suara Baby Bop)Jeff Brooks (2004)Kyle Nelson (2009; sut B.J.)Patty Wirtz (suara B.J.)Adam Brown (sut Riff)Michaela Dietz (suara Riff)Negara asalAmerika...

 

この項目には、一部のコンピュータや閲覧ソフトで表示できない文字が含まれています(詳細)。 数字の大字(だいじ)は、漢数字の一種。通常用いる単純な字形の漢数字(小字)の代わりに同じ音の別の漢字を用いるものである。 概要 壱万円日本銀行券(「壱」が大字) 弐千円日本銀行券(「弐」が大字) 漢数字には「一」「二」「三」と続く小字と、「壱」「�...

 

Эта статья о районе Лондона; о посёлке в графстве Девоншир см. Брикстон (Девон). Брикстон (Brixton)англ. Brixton Ламбет Первое упоминание 1062 г. Население 78 536 чел. Почтовые индексы SW2, SW9 Телефонные коды 020  Медиафайлы на Викискладе Бри́кстон (англ. Brixton) — район в южно�...

本條目存在以下問題,請協助改善本條目或在討論頁針對議題發表看法。 此條目需要擴充。 (2013年1月1日)请協助改善这篇條目,更進一步的信息可能會在討論頁或扩充请求中找到。请在擴充條目後將此模板移除。 此條目需要补充更多来源。 (2013年1月1日)请协助補充多方面可靠来源以改善这篇条目,无法查证的内容可能會因為异议提出而被移除。致使用者:请搜索一下条目的...

 

Operational United States Navy airfield from 1943 to 1950s For other uses, see No Man's Land (disambiguation). No Man's Land Navy AirfieldUSGS photo of Noman's Land with the field visible in the Southwest cornerIATA: noneICAO: noneSummaryAirport typeMilitary: AirfieldOperatorUnited States NavyLocationNomans Land, MassachusettsBuilt1943In use1943-1950sOccupantsNavyElevation AMSL37 ft / 11 mCoordinates41°15′12.8″N 070°49′25.04″W / 41.253556°N 70.8236222...

 

Kind of numerical parameter of a parametric family of probability distributions In probability theory and statistics, a shape parameter (also known as form parameter)[1] is a kind of numerical parameter of a parametric family of probability distributions[2] that is neither a location parameter nor a scale parameter (nor a function of these, such as a rate parameter). Such a parameter must affect the shape of a distribution rather than simply shifting it (as a location paramete...

Julius Maada BioBio pada tahun 2023 Presiden Sierra LeonePetahanaMulai menjabat 4 April 2018Wakil PresidenMohamed Juldeh JallohKetua MenteriDavid J. FrancisJacob Jusu SaffaPendahuluErnest Bai KoromaPenggantiPetahanaKetua Dewan Pemerintahan Nasional SementaraMasa jabatan16 Januari 1996 – 29 Maret 1996WakilKomba MondehPendahuluValentine StrasserPenggantiAhmad Tejan KabbahWakil Ketua Dewan Pemerintahan Nasional SementaraMasa jabatanJuni 1993 – Maret 1995ChairmanValentin...

 

Rocket League Championship SeriesJeu Rocket LeagueOrganisateur PsyonixPériodicité Semestrielle (2016-2020) Annuelle (2020-)Création 2016Tenant du titre Team VitalitySite web esports.rocketleague.commodifier - modifier le code - modifier Wikidata Les Rocket League Championship Series (RLCS) sont des tournois de sport électronique organisés par Psyonix sur le jeu Rocket League. Il s'agit des tournois les plus prestigieux de Rocket League car il s’agit des Championnats du monde de Rocket ...

 

Not to be confused with Sootoro. SutoroܣܘܬܪܐActive2012–presentCountrySyriaAllegianceSyriac Union Party (Syria)Autonomous Administration of North and East SyriaTypePoliceRoleSecurity and policingSize1,000+ (June 2013)[1]Garrison/HQAl-Malikiyah, Hasakah Governorate, SyriaNickname(s)SutoroWebsitehttps://www.facebook.com/Sutoro.S.S.F/CommandersGeneral commander, 2015Ashur Abu Sarkun[2]SpokespersonMalki Rabo[2]Military unit The Syriac Security Office (Syriac: ܡܟܬ�...

أحمد موسى معلومات شخصية الاسم الكامل أحمد موسى علي الميلاد 17 سبتمبر 1993 (العمر 30 سنة)البحرين مركز اللعب الوسط المحوري الجنسية البحرين  معلومات النادي النادي الحالي المنامة مسيرة الشباب سنوات فريق 2011-2007 المنامة المسيرة الاحترافية1 سنوات فريق م. (هـ.) 2011– المنامة 1 عدد مرات ...

 

British actor John ArnattBornJohn Edwin Arnatt(1917-05-09)9 May 1917Petrograd, RussiaDied21 December 1999(1999-12-21) (aged 82)Surrey, England, UKNationalityBritishOccupationActorSpouses Betty Huntley-Wright ​ ​(m. 1948, divorced)​ Sheila Tracy ​(m. 1962)​ Children1 John Edwin Arnatt (9 May 1917 – 21 December 1999) was a British actor.[1] Early life and education John Arnatt was born in Petrograd, Russia on...

 

Italian Navy officer Luciano ZappataAllegiance ItalyService/branch Italian NavyRankAdmiralCommands held Deputy Supreme Allied Commander Transformation Deputy Chief of Staff of the Navy Admiral Luciano Zappata is an Italian Navy officer who served as Deputy Supreme Allied Commander Transformation.[1] He graduated from the Naval Academy in 1970 From 1987 to 1988, he commanded the frigate ITS Espero and from 1992 to 1993 served as commanding officer of the cruiser ITS Vittorio ...

Litium aluminium hidrida Model gambar rangka litium aluminium hidrida Model bola-dan-pasak satuan sel litium aluminium hidrida Nama Nama IUPAC (preferensi) Litium tetrahidridoaluminat(III) Nama IUPAC (sistematis) Lithium alumanuida Nama lain Litium aluminium hidrida Lithal Litium alanat Litium aluminohidrida Litium tetrahidridoaluminat Litium tetrahidridoaluminat(III) Penanda Nomor CAS 16853-85-3 Y14128-54-2 (2H4) Y Model 3D (JSmol) Gambar interaktif 3DMet {{{3DMet}}} Singkata...

 

В Википедии есть статьи о других людях с такой фамилией, см. Карадемир. Тугба Карадемиртур. Tuğba Karademir Персональные данные Гражданство Турция Дата рождения 17 марта 1985(1985-03-17) (39 лет) Место рождения Анкара Рост 165 см Бывшиетренеры Роберт Тебби Место проживания Берри (Онтарио, �...