Skip to main content
Fachgebiete
Automobil + Motoren Bauwesen + Immobilien Business IT + Informatik Elektrotechnik + Elektronik Energie + Nachhaltigkeit Finance + Banking Management + Führung Marketing + Vertrieb Maschinenbau + Werkstoffe Versicherung + Risiko
DE
EN
Themenseiten
Organisationspsychologie Projektmanagement Marketing Smart Manufacturing
Bücher
Zeitschriften
Weitere Formate
Podcasts Webinare Technik Webinare Wirtschaft Kongresse Veranstaltungskalender Awards
Jetzt Einzelzugang starten
Zugang für Unternehmen
Referenzkunden
MTZ-Fachkongress

Antriebe und Energiesysteme von morgen


Austausch von Automobil- und Energiewirtschaft

Am 14./15. Mai geht es in Chemnitz um die Mobilitätswende durch Elektro- und Wasserstofffahrzeuge.
Erweiterte Suche
Anmelden
nach oben
Erschienen in:
Prerequisites and Notation Kapitel lesen Erstes Kapitel lesen

2016 | OriginalPaper | Buchkapitel

10. Number Theory in Public Key Cryptography

verfasst von : Alko R. Meijer

Erschienen in: Algebra for Cryptologists

Verlag: Springer International Publishing

Einloggen

Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.

search-config
loading …

Abstract

We have already dealt with two of the most important applications of number theory, namely the difficulty of factoring as used in the RSA public key system, and the difficulty of the discrete logarithm problem in Diffie–Hellman key establishment and ElGamal encryption. It is worthwhile recalling that until as recently as 1976, when Diffie and Hellman’s famous paper appeared, it was generally thought to be impossible to encrypt a message from Alice to Bob, if Alice and Bob had not previously obtained a secret key. Until then number theory was seen as the “Queen of Mathematics”, which is how Gauss described it, and as one would like a queen to be, this could (somewhat rudely) be construed as meaning “beautiful, but of no practical value”.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

  • über 102.000 Bücher
  • über 537 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Maschinenbau + Werkstoffe
  • Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 390 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Maschinenbau + Werkstoffe




 

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 340 Zeitschriften

aus folgenden Fachgebieten:

  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Versicherung + Risiko




Jetzt Wissensvorsprung sichern!

Jetzt informieren
Vorheriges Kapitel Applications to Block Ciphers
Nächstes Kapitel Where Do We Go from Here?
Fußnoten
1
Shamir, A.: How to share a secret Comm. ACM 22 (1979), pp. 612–613.
 
2
Note that we are only dealing with a group homomorphism. We are not concerned with ring properties here.
 
3
You thought we weren’t getting anywhere, didn’t you?!
 
4
“Residuosity” must be one of the ugliest words in the English language, but this author declines all responsibility for creating it.
 
5
This is the technical term used, but it may easily be misinterpreted: the scheme itself is not proved to be secure. What is proved is only that the difficulty of breaking the scheme is the same as the difficulty of some well known mathematical problem, which, with advancing knowledge, may turn out not to be all that difficult after all!
This terminology has its critics, see for example the paper by N. Koblitz and A. Menezes, Another look at “provable security,” J. Cryptology 20 (2007), pp. 3–37 and the reactions it provoked. You may also find interesting the paper by Neal Koblitz: The uneasy relationship between mathematics and cryptography, Notices of the Amer. Math. Soc., 54 (2007), pp. 972–979 and the reactions in the letters to the editor of the AMS notices.
 
6
Classical RSA, as should be evident, did not satisfy this requirement. An encryption system may be defined as semantically secure if, given the encryption of one of two messages m 0 and m 1, chosen by the adversary, he/she cannot determine (with a probability of success different from \(\frac{1} {2}\)) which plaintext was encrypted. In the asymmetric case, semantic security clearly implies probabilistic (since the adversary can find the encryption of any non-randomised message), but the converse is not true in general.
For example, using the notation of Sect. 4.​4.​1 for ElGamal encryption and \(\mathbb{Z}_{p}^{{\ast}}\) as our group, the encryption of a message m is the pair < c 1, c 2 > where c 1 = g k and c 2 = my A k . Using our knowledge of the Legendre symbol, and the fact that g cannot be a square, since it is a generator of the group, we see that \((\frac{g} {p}) = -1\). This gives us the parity of the randomly selected k, as we can easily find \(\frac{c_{1}} {p}\). We also compute \((\frac{c_{2}} {p} )\). But then we can find the parity of \(\frac{m} {p}\), so, given a ciphertext, we can determine which of m 0 and m 1 was encrypted if these are a quadratic residue and non-residue respectively. Thus ElGamal encryption in this simple form is, although probabilistic, not semantically secure.
 
7
And presumably goes back to the lawyer who was handling the divorce. It must be noted here that Alice and Bob, known as the first couple of Cryptology, appear to have gotten together later, since there are numerous later protocols in which they happily communicate.
 
8
The loser gets custody of the teenage children.
 
9
A spy has two secrets that he is willing to sell to us. But, as we suspect him of being a double agent, we don’t want him to know what matter we are really interested in.
 
10
This seems silly, but we are only showing what can be done in principle.
 
11
Some previously agreed upon padding is probably required, and if Alice is using RSA, she must have sent the public key to Bob in step 1, and encrypt under the private key.
 
12
The same is obviously true for the Modified Rabin generator of Exercise 5 in Sect. 10.6.
 
Metadaten
Titel
Number Theory in Public Key Cryptography
verfasst von
Alko R. Meijer
Copyright-Jahr
2016
Buch
Algebra for Cryptologists

Print ISBN: 978-3-319-30395-6

Electronic ISBN: 978-3-319-30396-3

Copyright-Jahr: 2016

DOI
https://doi.org/10.1007/978-3-319-30396-3_10

Premium Partner

    Bildnachweise