Misplaced Pages

#960039

86-436: Traditionally, secure encrypted communication between two parties required that they first exchange keys by some secure physical means, such as paper key lists transported by a trusted courier . The Diffie–Hellman key exchange method allows two parties that have no prior knowledge of each other to jointly establish a shared secret key over an insecure channel . This key can then be used to encrypt subsequent communications using

172-460: A Sophie Germain prime q is sometimes used to calculate p = 2 q + 1 , called a safe prime , since the order of G is then only divisible by 2 and q . Sometimes g is chosen to generate the order q subgroup of G , rather than G , so that the Legendre symbol of g never reveals the low order bit of a . A protocol using such a choice is for example IKEv2 . The generator g is often

258-624: A and b respectively, with public keys A and B , as well as the ephemeral key pairs x, X and y, Y . Then protocol is: The long term public keys need to be transferred somehow. That can be done beforehand in a separate, trusted channel, or the public keys can be encrypted using some partial key agreement to preserve anonymity. For more of such details as well as other improvements like side channel protection or explicit key confirmation , as well as early messages and additional password authentication, see e.g. US patent "Advanced modular handshake for key agreement and optional authentication". X3DH

344-584: A coprime to n , there is some integer k for which g ≡ a (mod  n ). Such a value k is called the index or discrete logarithm of a to the base g modulo n . So g is a primitive root modulo   n if and only if g is a generator of the multiplicative group of integers modulo n . Gauss defined primitive roots in Article 57 of the Disquisitiones Arithmeticae (1801), where he credited Euler with coining

430-718: A denial-of-service attack (DoS) against the protocol variants use ephemeral keys, called D(HE)at attack. The attack exploits that the Diffie–Hellman key exchange allows attackers to send arbitrary numbers that are actually not public keys, triggering expensive modular exponentiation calculations on the victim's side. Another CVEs released disclosed that the Diffie–Hellman key exchange implementations may use long private exponents ( CVE-2022-40735 ) that arguably make modular exponentiation calculations unnecessarily expensive or may unnecessary check peer's public key ( CVE-2024-41996 ) has similar resource requirement as key calculation using

516-440: A given only g , p and g mod p . Such a problem is called the discrete logarithm problem . The computation of g mod p is known as modular exponentiation and can be done efficiently even for large numbers. Note that g need not be large at all, and in practice is usually a small integer (like 2, 3, ...). The chart below depicts who knows what, again with non-secret values in blue , and secret values in red . Here Eve

602-425: A hub and spoke model. Couriers services utilizing courier software provide electronic proof of delivery and electronic tracking details. In ancient history, messages were hand-delivered using a variety of methods, including runners , homing pigeons and riders on horseback. Before the introduction of mechanized courier services, foot messengers physically ran miles to their destinations. Xenophon attributed

688-547: A symmetric-key cipher . Diffie–Hellman is used to secure a variety of Internet services. However, research published in October 2015 suggests that the parameters in use for many DH Internet applications at that time are not strong enough to prevent compromise by very well-funded attackers, such as the security services of some countries. The scheme was published by Whitfield Diffie and Martin Hellman in 1976, but in 1997 it

774-475: A 2019 quarterly earnings call, the CEO of FedEx named Amazon as a direct competitor, cementing the e- commerce company's growth into the field of logistics. Primitive root modulo n In modular arithmetic , a number g is a primitive root modulo  n if every number a coprime to n is congruent to a power of g modulo n . That is, g is a primitive root modulo   n if for every integer

860-546: A Diffie–Hellman agreement as follows, with all operations taken to be modulo p : An eavesdropper has been able to see g mod p , g mod p , g mod p , g mod p , g mod p , and g mod p , but cannot use any combination of these to efficiently reproduce g mod p . To extend this mechanism to larger groups, two basic principles must be followed: These principles leave open various options for choosing in which order participants contribute to keys. The simplest and most obvious solution

946-604: A country-wide service is Australia Post. Australian Post operates quite differently to government departments, as it is government-owned enterprise focused on service delivery in a competitive market. It operates in a fully competitive market against other delivery services such as Fastway , UPS , and Transdirect . International courier services in China include TNT , EMS International , DHL , FedEx and UPS. These companies provide nominal worldwide service for both inbound and outbound shipments, connecting China to countries such as

SECTION 10

#1732773116961

1032-461: A courier has changed; it is no longer a lengthy task of making numerous calls to different courier companies to request a quote. Booking a courier is predominantly carried out online. The courier industry has been quick to adapt to an ever-changing digital landscape, meeting the needs of mobile and desktop consumers as well as e-commerce and online retailers, offering end users access to instant online payments, parcel tracking, delivery notifications, and

1118-466: A delivery deadline, loss of life from a delayed organ transplant). The courier business in Australia is a very competitive industry and is mainly concentrated in the high population areas in and around the capital cities. With such a vast mass of land to cover the courier companies tend to transport either by air or by the main transport routes and national highways. The only large company that provides

1204-568: A given integer a that is neither a perfect square nor −1 is a primitive root modulo infinitely many primes . No simple general formula to compute primitive roots modulo n is known. There are however methods to locate a primitive root that are faster than simply trying out all candidates. If the multiplicative order (its exponent ) of a number m modulo n is equal to φ ( n ) {\displaystyle \varphi (n)} (the order of Z {\displaystyle \mathbb {Z} } n ), then it

1290-409: A handful of groups that are of order 1024 bits or less. By precomputing the first three steps of the number field sieve for the most common groups, an attacker need only carry out the last step, which is much less computationally expensive than the first three steps, to obtain a specific logarithm. The Logjam attack used this vulnerability to compromise a variety of Internet services that allowed

1376-401: A long exponent. An attacker can exploit both vulnerabilities together. The number field sieve algorithm, which is generally the most effective in solving the discrete logarithm problem , consists of four computational steps. The first three steps only depend on the order of the group G, not on the specific number whose finite log is desired. It turns out that much Internet traffic uses one of

1462-433: A moment's notice anywhere in the world, usually via commercial airlines. While this type of service is the second costliest— general aviation charters are far more expensive—companies analyze the cost of service to engage an on-board courier versus the "cost" the company will realize should the product not arrive by a specified time (an assembly line stopping, untimely court filing, lost sales from product or components missing

1548-709: A point on an elliptic curve instead of as an integer modulo n. Variants using hyperelliptic curves have also been proposed. The supersingular isogeny key exchange is a Diffie–Hellman variant that was designed to be secure against quantum computers , but it was broken in July 2022. The used keys can either be ephemeral or static (long term) key, but could even be mixed, so called semi-static DH. These variants have different properties and hence different use cases. An overview over many variants and some also discussions can for example be found in NIST SP 800-56A. A basic list: It

1634-524: A premium service, couriers are usually more expensive than standard mail services, and their use is normally limited to packages where one or more of these features are considered important enough to warrant the cost. Courier services operate on all scales, from within specific towns or cities, to regional, national and global services. Large courier companies include DHL , DTDC , FedEx , EMS International , TNT , UPS , India Post , J&T Express and Aramex . These offer services worldwide, typically via

1720-726: A protocol is the Secure Remote Password protocol . Courier A courier is a person or organization that delivers a message, package or letter from one place or person to another place or person. Typically, a courier provides their courier service on a commercial contract basis; however, some couriers are government or state agency employees (for example: a diplomatic courier ). Couriers are distinguished from ordinary mail services by features such as speed, security, tracking, signature, specialization and individualization of express services, and swift delivery times, which are optional for most everyday mail services. As

1806-463: A server, which Alice downloads and verifies the signature on. Alice then initiates the exchange to Bob. The OPK is optional. Diffie–Hellman key agreement is not limited to negotiating a key shared by only two participants. Any number of users can take part in an agreement by performing iterations of the agreement protocol and exchanging intermediate data (which does not itself need to be kept secret). For example, Alice, Bob, and Carol could participate in

SECTION 20

#1732773116961

1892-444: A small integer such as 2. Because of the random self-reducibility of the discrete logarithm problem a small g is equally secure as any other generator of the same group. If Alice and Bob use random number generators whose outputs are not completely random and can be predicted to some extent, then it is much easier to eavesdrop. In the original description, the Diffie–Hellman exchange by itself does not provide authentication of

1978-523: A week (former USSR countries). Large couriers often require an account to be held (and this can include daily scheduled collections). Senders are therefore primarily in the commercial/industrial sector (and not the general public); some couriers such as DHL do however allow public sending (at higher cost than regular senders). In recent years, the increased popularity of Black Friday in the UK has placed some firms under operational stress. The process of booking

2064-596: Is 123 ≡ − 1 ≡ μ ( 31 − 1 ) ( mod 31 ) {\displaystyle 123\equiv -1\equiv \mu (31-1){\pmod {31}}} . If a {\displaystyle a} is a primitive root modulo the prime p {\displaystyle p} , then a p − 1 2 ≡ − 1 ( mod p ) {\displaystyle a^{\frac {p-1}{2}}\equiv -1{\pmod {p}}} . Artin's conjecture on primitive roots states that

2150-409: Is prime , and g is a primitive root modulo p . These two values are chosen in this way to ensure that the resulting shared secret can take on any value from 1 to p –1. Here is an example of the protocol, with non-secret values in blue , and secret values in red . Both Alice and Bob have arrived at the same values because under mod p, More specifically, Only a and b are kept secret. All

2236-415: Is a $ 59 billion industry, with 90% of the business shared by DHL, FedEx, UPS and USA Couriers. On the other hand, regional and/or local courier and delivery services were highly diversified and tended to be smaller operations; the top 50 firms accounted for just a third of the sector's revenues. USPS is mail or packages delivered by the government and are the only ones who can legally ship to mailboxes. In

2322-434: Is a more general description of the protocol: Both Alice and Bob are now in possession of the group element g = g , which can serve as the shared secret key. The group G satisfies the requisite condition for secure communication as long as there is no efficient algorithm for determining g given g , g , and g . For example, the elliptic curve Diffie–Hellman protocol is a variant that represents an element of G as

2408-533: Is a primitive root. In fact the converse is true: If m is a primitive root modulo n , then the multiplicative order of m is φ ( n ) = λ ( n )   . {\displaystyle \varphi (n)=\lambda (n)~.} We can use this to test a candidate m to see if it is primitive. For n > 1 {\displaystyle n>1} first, compute φ ( n )   . {\displaystyle \varphi (n)~.} Then determine

2494-433: Is an eavesdropper – she watches what is sent between Alice and Bob, but she does not alter the contents of their communications. Now s is the shared secret key and it is known to both Alice and Bob, but not to Eve. Note that it is not helpful for Eve to compute AB , which equals g mod p . Note: It should be difficult for Alice to solve for Bob's private key or for Bob to solve for Alice's private key. If it

2580-2077: Is an odd prime and k > 0 . For all other values of n the multiplicative group of integers modulo n is not cyclic . This was first proved by Gauss . The number 3 is a primitive root modulo 7 because 3 1 = 3 0 × 3 ≡ 1 × 3 = 3 ≡ 3 ( mod 7 ) 3 2 = 3 1 × 3 ≡ 3 × 3 = 9 ≡ 2 ( mod 7 ) 3 3 = 3 2 × 3 ≡ 2 × 3 = 6 ≡ 6 ( mod 7 ) 3 4 = 3 3 × 3 ≡ 6 × 3 = 18 ≡ 4 ( mod 7 ) 3 5 = 3 4 × 3 ≡ 4 × 3 = 12 ≡ 5 ( mod 7 ) 3 6 = 3 5 × 3 ≡ 5 × 3 = 15 ≡ 1 ( mod 7 ) {\displaystyle {\begin{array}{rcrcrcrcrcr}3^{1}&=&3^{0}\times 3&\equiv &1\times 3&=&3&\equiv &3{\pmod {7}}\\3^{2}&=&3^{1}\times 3&\equiv &3\times 3&=&9&\equiv &2{\pmod {7}}\\3^{3}&=&3^{2}\times 3&\equiv &2\times 3&=&6&\equiv &6{\pmod {7}}\\3^{4}&=&3^{3}\times 3&\equiv &6\times 3&=&18&\equiv &4{\pmod {7}}\\3^{5}&=&3^{4}\times 3&\equiv &4\times 3&=&12&\equiv &5{\pmod {7}}\\3^{6}&=&3^{5}\times 3&\equiv &5\times 3&=&15&\equiv &1{\pmod {7}}\end{array}}} Here we see that

2666-478: Is called the group of units modulo n , or the group of primitive classes modulo n . As explained in the article multiplicative group of integers modulo n , this multiplicative group ( Z {\displaystyle \mathbb {Z} } n ) is cyclic if and only if n is equal to 2, 4, p , or 2 p where p is a power of an odd prime number . When (and only when) this group Z {\displaystyle \mathbb {Z} } n

Diffie–Hellman key exchange - Misplaced Pages Continue

2752-517: Is cyclic, a generator of this cyclic group is called a primitive root modulo n (or in fuller language primitive root of unity modulo n , emphasizing its role as a fundamental solution of the roots of unity polynomial equations X − 1 in the ring Z {\displaystyle \mathbb {Z} } n ), or simply a primitive element of Z {\displaystyle \mathbb {Z} } n . When Z {\displaystyle \mathbb {Z} } n

2838-551: Is equal to since, in general, a cyclic group with r elements has φ ( r ) {\displaystyle \varphi (r)} generators. For prime n , this equals φ ( n − 1 ) {\displaystyle \varphi (n-1)} , and since n / φ ( n − 1 ) ∈ O ( log ⁡ log ⁡ n ) {\displaystyle n/\varphi (n-1)\in O(\log \log n)}

2924-471: Is large enough. An efficient algorithm to solve the discrete logarithm problem would make it easy to compute a or b and solve the Diffie–Hellman problem, making this and many other public key cryptosystems insecure. Fields of small characteristic may be less secure. The order of G should have a large prime factor to prevent use of the Pohlig–Hellman algorithm to obtain a or b . For this reason,

3010-433: Is non-cyclic, such primitive elements mod n do not exist. Instead, each prime component of n has its own sub-primitive roots (see 15 in the examples below). For any n (whether or not Z {\displaystyle \mathbb {Z} } n is cyclic), the order of Z {\displaystyle \mathbb {Z} } n is given by Euler's totient function φ ( n ) (sequence A000010 in

3096-447: Is not difficult for Alice to solve for Bob's private key (or vice versa), then an eavesdropper, Eve , may simply substitute her own private / public key pair, plug Bob's public key into her private key, produce a fake shared secret key, and solve for Bob's private key (and use that to solve for the shared secret key). Eve may attempt to choose a public / private key pair that will make it easy for her to solve for Bob's private key. Here

3182-916: Is odd) is a primitive root modulo 2 p . Finding primitive roots modulo p is also equivalent to finding the roots of the ( p − 1)st cyclotomic polynomial modulo p . The least primitive root g p modulo p (in the range 1, 2, ..., p − 1 ) is generally small. Burgess (1962) proved that for every ε > 0 there is a C such that g p ≤ C p 1 4 + ε   . {\displaystyle g_{p}\leq C\,p^{{\frac {1}{4}}+\varepsilon }~.} Grosswald (1981) proved that if p > e e 24 ≈ 10 11504079571 {\displaystyle p>e^{e^{24}}\approx 10^{11504079571}} , then g p < p 0.499   . {\displaystyle g_{p}<p^{0.499}~.} Shoup (1990, 1992) proved, assuming

3268-474: Is often used in pseudorandom number generators and cryptography , including the Diffie–Hellman key exchange scheme. Sound diffusers have been based on number-theoretic concepts such as primitive roots and quadratic residues . The Disquisitiones Arithmeticae has been translated from Gauss's Ciceronian Latin into English and German. The German edition includes all of his papers on number theory: all

3354-485: Is possible to use ephemeral and static keys in one key agreement to provide more security as for example shown in NIST SP 800-56A, but it is also possible to combine those in a single DH key exchange, which is then called triple DH (3-DH). In 1997 a kind of triple DH was proposed by Simon Blake-Wilson, Don Johnson, Alfred Menezes in 1997, which was improved by C. Kudla and K. G. Paterson in 2005 and shown to be secure. The long term secret keys of Alice and Bob are denoted by

3440-463: Is prime, then the period of repetition is n − 1. Permutations created in this way (and their circular shifts) have been shown to be Costas arrays . If n is a positive integer, the integers from 1 to n − 1 that are coprime to n (or equivalently, the congruence classes coprime to n ) form a group , with multiplication modulo n as the operation; it is denoted by Z {\displaystyle \mathbb {Z} } n , and

3526-640: Is the ElGamal encryption . A more modern variant is the Integrated Encryption Scheme . Protocols that achieve forward secrecy generate new key pairs for each session and discard them at the end of the session. The Diffie–Hellman key exchange is a frequent choice for such protocols, because of its fast key generation. When Alice and Bob share a password, they may use a password-authenticated key agreement (PK) form of Diffie–Hellman to prevent man-in-the-middle attacks. One simple scheme

Diffie–Hellman key exchange - Misplaced Pages Continue

3612-485: Is the Möbius function . For example, E.g., the product of the latter primitive roots is 2 6 ⋅ 3 4 ⋅ 7 ⋅ 11 2 ⋅ 13 ⋅ 17 = 970377408 ≡ 1 ( mod 31 ) {\displaystyle 2^{6}\cdot 3^{4}\cdot 7\cdot 11^{2}\cdot 13\cdot 17=970377408\equiv 1{\pmod {31}}} , and their sum

3698-847: Is the special product of a co-operative arrangement between China Post and Alipay , which is the online payment unit of Alibaba Group . It is only available for the delivery of online purchases made using Alipay. Within the Municipality of Beijing, TongCheng KuaiDi (同城快递), also a unit of China Post, provides intra-city service using cargo bicycles . International courier services in India include DHL , FedEx , Blue Dart Express , Spicexpress and Logistics Pvt Ltd , Ekart , DTDC , VRL Courier Services , Delhivery , TNT , Amazon.com , OCS and Gati Ltd . Apart from these, several local couriers also operate across India. Almost all of these couriers can be tracked online. India Post , an undertaking by

3784-399: Is to arrange the N participants in a circle and have N keys rotate around the circle, until eventually every key has been contributed to by all N participants (ending with its owner) and each participant has contributed to N keys (ending with their own). However, this requires that every participant perform N modular exponentiations. By choosing a more desirable order, and relying on

3870-517: Is to compare the hash of s concatenated with the password calculated independently on both ends of channel. A feature of these schemes is that an attacker can only test one specific password on each iteration with the other party, and so the system provides good security with relatively weak passwords. This approach is described in ITU-T Recommendation X.1035 , which is used by the G.hn home networking standard. An example of such

3956-545: The Middle Ages , royal courts maintained their own messengers who were paid little more than common labourers. In cities, there are often bicycle couriers or motorcycle couriers but for consignments requiring delivery over greater distance networks, this may often include trucks , railroads and aircraft . Many companies which operate under a just-in-time or "JIT" inventory method often use on-board couriers (OBCs). On-board couriers are individuals who can travel at

4042-524: The OEIS ). And then, Euler's theorem says that a ≡ 1 (mod n ) for every a coprime to n ; the lowest power of a that is congruent to 1 modulo n is called the multiplicative order of a modulo n . In particular, for a to be a primitive root modulo n , a has to be the smallest power of a that is congruent to 1 modulo n . For example, if n = 14 then the elements of Z {\displaystyle \mathbb {Z} } n are

4128-645: The US , Australia , United Kingdom , and New Zealand . Of the international courier services, the Dutch company TNT is considered to have the most capable local fluency and efficacy for third- and fourth- tiered cities. EMS International is a unit of China Post, and as such is not available for shipments originating outside China. Domestic courier services include SF Express , STO Express (申通), ZTO Express (中通), YTO Express (圆通), E- EMS (E邮宝), Cainiao Express (菜鸟) and many other operators of sometimes microscopic scales. E-EMS,

4214-428: The cipher suite ). The method was followed shortly afterwards by RSA , an implementation of public-key cryptography using asymmetric algorithms. Expired US patent 4,200,770 from 1977 describes the now public-domain algorithm. It credits Hellman, Diffie, and Merkle as inventors. In 2006, Hellman suggested the algorithm be called Diffie–Hellman–Merkle key exchange in recognition of Ralph Merkle 's contribution to

4300-402: The generalized Riemann hypothesis , that g p = O(log p ). Fridlander (1949) and Salié (1950) proved that there is a positive constant C such that for infinitely many primes g p > C log p . It can be proved in an elementary manner that for any positive integer M there are infinitely many primes such that M < g p < p − M . A primitive root modulo n

4386-430: The period of 3 modulo 7 is 6. The remainders in the period, which are 3, 2, 6, 4, 5, 1, form a rearrangement of all nonzero remainders modulo 7, implying that 3 is indeed a primitive root modulo 7. This derives from the fact that a sequence ( g modulo  n ) always repeats after some value of k , since modulo  n produces a finite number of values. If g is a primitive root modulo  n and n

SECTION 50

#1732773116961

4472-634: The Indian government, is the largest courier service with around 155 thousand branches (comprising 139 thousand (90%) in rural areas and 16 thousand (10%) in urban areas). All couriers use the PIN code or postal index number introduced by India Post to locate delivery address. Additionally, the contact number of the recipient and sender are voluntarily added on the courier for ease of locating the address. The history of courier services in Bangladesh dates back to

4558-507: The Logjam authors recommend use of elliptic curve cryptography , for which no similar attack is known. Failing that, they recommend that the order, p , of the Diffie–Hellman group should be at least 2048 bits. They estimate that the pre-computation required for a 2048-bit prime is 10 times more difficult than for 1024-bit primes. Public key encryption schemes based on the Diffie–Hellman key exchange have been proposed. The first such scheme

4644-403: The UK every day. In fact, from 1988 to 2016, UK couriers were considered universally self employed, though the number of salaried couriers employed by firms has grown substantially since then. However, since the dawn of the electronic age the way in which businesses use couriers has changed dramatically. Prior to email and the ability to create PDFs, documents represented a significant proportion of

4730-510: The UK same-day courier market stems from the London Taxi companies but soon expanded into dedicated motorcycle despatch riders with the taxi companies setting up separate arms to their companies to cover the courier work. During the late 1970s small provincial and regional companies were popping up throughout the country. Today, there are many large companies offering next-day courier services. There are many 'specialist' couriers usually for

4816-662: The West, making a Wells Fargo office in every camp and settlement a necessity for commerce and connections to home. Shortly afterward, the Pony Express was established to move packages more quickly than the traditional stagecoach . It illustrated the demand for timely deliveries across the nation, a concept that continued to evolve with the railroads , automobiles and interstate highways and which has emerged into today's courier industry. The courier industry in United States

4902-465: The analogy back to a real-life exchange using large numbers rather than colors, this determination is computationally expensive. It is impossible to compute in a practical amount of time even for modern supercomputers . The simplest and the original implementation, later formalized as Finite Field Diffie–Hellman in RFC 7919 , of the protocol uses the multiplicative group of integers modulo p , where p

4988-454: The beginning and continuing to be so, actively decrypting and re-encrypting messages every time Alice and Bob communicate. If she arrives after the keys have been generated and the encrypted conversation between Alice and Bob has already begun, the attack cannot succeed. If she is ever absent, her previous presence is then revealed to Alice and Bob. They will know that all of their private conversations had been intercepted and decoded by someone in

5074-712: The business. However, over the past five years, documentation revenues have decreased by 50 percent. Customers are also demanding more from their courier partners. Therefore, more organisations prefer to use the services of larger organisations who are able to provide more flexibility and levels of service, which has led to another level of courier company, regional couriers. This is usually a local company which has expanded to more than one office to cover an area. Some UK couriers offer next-day services to other European countries. FedEx offers next-day air delivery to many EU countries. Cheaper 'by-road' options are also available, varying from two days' delivery time (such as France), to up to

5160-407: The channel. In most cases it will not help them get Mallory's private key, even if she used the same key for both exchanges. A method to authenticate the communicating parties to each other is generally needed to prevent this type of attack. Variants of Diffie–Hellman, such as STS protocol , may be used instead to avoid these types of attacks. A CVE released in 2021 ( CVE-2002-20001 ) disclosed

5246-416: The color is yellow. Each person also selects a secret color that they keep to themselves – in this case, red and cyan. The crucial part of the process is that Alice and Bob each mix their own secret color together with their mutually shared color, resulting in orange-tan and light-blue mixtures respectively, and then publicly exchange the two mixed colors. Finally, each of them mixes the color they received from

SECTION 60

#1732773116961

5332-408: The communicating parties and can be vulnerable to a man-in-the-middle attack . Mallory (an active attacker executing the man-in-the-middle attack) may establish two distinct key exchanges, one with Alice and the other with Bob, effectively masquerading as Alice to Bob, and vice versa, allowing her to decrypt, then re-encrypt, the messages passed between them. Note that Mallory must be in the middle from

5418-643: The congruence classes {1, 2, 4, 7, 8, 11, 13, 14}; there are φ (15) = 8 of them. Since there is no number whose order is 8, there are no primitive roots modulo 15. Indeed, λ (15) = 4 , where λ is the Carmichael function . (sequence A002322 in the OEIS ) Numbers n {\displaystyle n} that have a primitive root are of the shape These are the numbers n {\displaystyle n} with φ ( n ) = λ ( n ) , {\displaystyle \varphi (n)=\lambda (n),} kept also in

5504-406: The congruence classes {1, 3, 5, 9, 11, 13}; there are φ (14) = 6 of them. Here is a table of their powers modulo 14: The order of 1 is 1, the orders of 3 and 5 are 6, the orders of 9 and 11 are 3, and the order of 13 is 2. Thus, 3 and 5 are the primitive roots modulo 14. For a second example let n = 15 . The elements of Z {\displaystyle \mathbb {Z} } 15 are

5590-525: The convenience of door to door collection and delivery to almost any destination in the world. The courier industry has long held an important place in United States commerce and has been involved in pivotal moments in the nation's history such as westward migration and the gold rush . Wells Fargo was founded in 1852 and rapidly became the preeminent package delivery company. The company specialised in shipping gold, packages and newspapers throughout

5676-1066: The country's logistics and trade networks. Couriers that operate across Bangladesh include Sundarban Courier Service (40% market share), SA Paribahan , Pathao Courier , e-dak Courier , RedX , Sheba Delivery , Janani Express Parcel Service , Delivery Tiger , eCourier , Karatoa Courier Service , Sonar Courier . Almost all of these couriers can be tracked online. Also international courier services in Bangladesh include DHL , FedEx , United Express , Royale International Bangladesh , DSL Worldwide Courier Service , Aramex , Pos Laju , J&T Express , and Amazon.com . International courier services in Malaysia include DHL , FedEx , Pgeon , Skynet Express , ABX Express , GDex , Pos Laju , J&T Express , and Amazon.com . Apart from these, several local couriers also operate across Malaysia. Almost all of these couriers can be tracked online. The main courier services available in Ireland as alternatives to

5762-399: The different prime factors of φ ( n ) {\displaystyle \varphi (n)} , say p 1 , ..., p k . Finally, compute using a fast algorithm for modular exponentiation such as exponentiation by squaring . A number g for which these k results are all different from 1 is a primitive root. The number of primitive roots modulo n , if there are any,

5848-425: The discrete log problem for a 1024-bit prime would cost on the order of $ 100 million, well within the budget of a large national intelligence agency such as the U.S. National Security Agency (NSA). The Logjam authors speculate that precomputation against widely reused 1024-bit DH primes is behind claims in leaked NSA documents that NSA is able to break much of current cryptography. To avoid these vulnerabilities,

5934-405: The eight implied by a simple circular arrangement. The protocol is considered secure against eavesdroppers if G and g are chosen properly. In particular, the order of the group G must be large, particularly if the same group is used for large amounts of traffic. The eavesdropper has to solve the Diffie–Hellman problem to obtain g . This is currently considered difficult for groups whose order

6020-411: The fact that keys can be duplicated, it is possible to reduce the number of modular exponentiations performed by each participant to log 2 ( N ) + 1 using a divide-and-conquer-style approach, given here for eight participants: Once this operation has been completed all participants will possess the secret g , but each participant will have performed only four modular exponentiations, rather than

6106-706: The first use of couriers to the Persian prince Cyrus the Younger . Famously, the Ancient Greek courier Pheidippides is said to have run 26 miles from Marathon to Athens to bring the news of the Greek victory over the Persians in 490 BCE. The long-distance race known as a marathon is named for this run. Judah's king, Hezekiah, dates between 200 and 400 BCE, where several couriers brought letters throughout

6192-455: The generators are very common among {2, ..., n −1} and thus it is relatively easy to find one. If g is a primitive root modulo p , then g is also a primitive root modulo all powers p unless g ≡ 1 (mod p ); in that case, g + p is. If g is a primitive root modulo p , then g is also a primitive root modulo all smaller powers of p . If g is a primitive root modulo p , then either g or g + p (whichever one

6278-476: The invention of public-key cryptography (Hellman, 2006), writing: The system...has since become known as Diffie–Hellman key exchange. While that system was first described in a paper by Diffie and me, it is a public key distribution system, a concept developed by Merkle, and hence should be called 'Diffie–Hellman–Merkle key exchange' if names are to be associated with it. I hope this small pulpit might help in that endeavor to recognize Merkle's equal contribution to

6364-474: The invention of public key cryptography. Diffie–Hellman key exchange establishes a shared secret between two parties that can be used for secret communication for exchanging data over a public network. An analogy illustrates the concept of public key exchange by using colors instead of very large numbers: The process begins by having the two parties, Alice and Bob , publicly agree on an arbitrary starting color that does not need to be kept secret. In this example,

6450-905: The land of Judah and Israel (cf. 2 Chron 30 ESV). Starting at the time of Augustus , the ancient Greeks and Romans made use of a class of horse and chariot -mounted couriers called anabasii to quickly bring messages and commands from long distances. The word anabasii comes from the Greek ἀνάβασις ( anábasis , "ascent, mounting"). They were contemporary with the Greek hemeredromi , who carried their messages by foot. In Roman Britain , Rufinus made use of anabasii, as documented in Saint Jerome 's memoirs ( adv. Ruffinum , l. 3. c. 1.): "Idcircone Cereales et Anabasii tui per diversas provincias cucurrerunt, ut laudes meas legerent?" ("Is it on that account that your Cereales and Anabasii circulated through many provinces, so that they might read my praises?") In

6536-463: The late 1970s when private companies started offering delivery and parcel services. These companies played a crucial role in facilitating the movement of documents and goods within the country. Over the years, the courier industry in Bangladesh has grown significantly, adapting to changes in technology and expanding its services to include international shipments. Today, various local and international courier companies operate in Bangladesh, contributing to

6622-494: The national An Post system are Parcel Direct Ireland , DHL , UPS, TNT , DPD and FedEx. There are several international courier companies in Singapore including TNT, DHL and FedEx. Despite being a small country, the demand for courier services is high. Many local courier companies have sprung up to meet this demand. Most courier companies in Singapore focus on local deliveries instead of international freight. The genus of

6708-405: The other values – p , g , g mod p , and g mod p – are sent in the clear. The strength of the scheme comes from the fact that g mod p = g mod p take extremely long times to compute by any known algorithm just from the knowledge of p , g , g mod p , and g mod p . Such a function that is easy to compute but hard to invert is called a one-way function . Once Alice and Bob compute

6794-406: The partner with their own private color. The result is a final color mixture (yellow-brown in this case) that is identical to their partner's final color mixture. If a third party listened to the exchange, they would only know the common color (yellow) and the first mixed colors (orange-tan and light-blue), but it would be very hard for them to find out the final secret color (yellow-brown). Bringing

6880-443: The sequence A033948 in the OEIS . The following table lists the primitive roots modulo n up to n = 31 {\displaystyle n=31} : Gauss proved that for any prime number p (with the sole exception of p = 3), the product of its primitive roots is congruent to 1 modulo p . He also proved that for any prime number p , the sum of its primitive roots is congruent to μ ( p − 1) modulo p , where μ

6966-431: The shared secret they can use it as an encryption key, known only to them, for sending messages across the same open communications channel. Of course, much larger values of a , b , and p would be needed to make this example secure, since there are only 23 possible results of n mod 23. However, if p is a prime of at least 600 digits, then even the fastest modern computers using the fastest known algorithm cannot find

7052-471: The term. In Article 56 he stated that Lambert and Euler knew of them, but he was the first to rigorously demonstrate that primitive roots exist for a prime n . In fact, the Disquisitiones contains two proofs: The one in Article 54 is a nonconstructive existence proof , while the proof in Article 55 is constructive . A primitive root exists if and only if n is 1, 2, 4, p or 2 p , where p

7138-497: The transportation of items such as freight/pallets, sensitive documents and liquids. The 'Man & Van'/Freelance courier business model, is highly popular in the United Kingdom, with thousands upon thousands of independent couriers and localised companies, offering next-day and same day services. This is likely to be so popular because of the low business requirements (a vehicle) and the lucrative number of items sent within

7224-409: The use of groups whose order was a 512-bit prime number, so called export grade . The authors needed several thousand CPU cores for a week to precompute data for a single 512-bit prime. Once that was done, individual logarithms could be solved in about a minute using two 18-core Intel Xeon CPUs. As estimated by the authors behind the Logjam attack, the much more difficult precomputation needed to solve

7310-567: Was initially proposed as part of the Double Ratchet Algorithm used in the Signal Protocol . The protocol offers forward secrecy and cryptographic deniability. It operates on an elliptic curve. The protocol uses five public keys. Alice has an identity key IK A and an ephemeral key EK A . Bob has an identity key IK B , a signed prekey SPK B , and a one-time prekey OPK B . Bob first publishes his three keys to

7396-630: Was revealed that James H. Ellis , Clifford Cocks , and Malcolm J. Williamson of GCHQ , the British signals intelligence agency, had previously shown in 1969 how public-key cryptography could be achieved. Although Diffie–Hellman key exchange itself is a non-authenticated key-agreement protocol , it provides the basis for a variety of authenticated protocols, and is used to provide forward secrecy in Transport Layer Security 's ephemeral modes (referred to as EDH or DHE depending on

#960039