Poly1305

Key takeaways

Poly1305 belongs to computer science; place it in that map before memorising details.
Learn the definition first, then one example that makes the definition concrete.
Connect Poly1305 to a quantity you can measure, compute or draw — that is where exam questions come from.
Reproduce the core statement of Poly1305 from memory before moving on to harder problems.

Reference excerpt

Poly1305 is a universal hash family designed by Daniel J. Bernstein in 2002 for use in cryptography. As with any universal hash family, Poly1305 can be used as a one-time message authentication code to authenticate a single message using a secret key shared between sender and recipient, similar to the way that a one-time pad can be used to conceal the content of a single message using a secret key shared between sender and recipient. Originally Poly1305 was proposed as part of Poly1305-AES, a Carter–Wegman authenticator that combines the Poly1305 hash with AES-128 to authenticate many messages using a single short key and distinct message numbers. Poly1305 was later applied with a single-use key generated for each message using XSalsa20 in the NaCl crypto_secretbox_xsalsa20poly1305 authenticated cipher, and then using ChaCha in the ChaCha20-Poly1305 authenticated cipher deployed in TLS on the internet.

Description

Definition of Poly1305 Poly1305 takes a 16-byte secret key r {\displaystyle r} and an L {\displaystyle L} -byte message m {\displaystyle m} and returns a 16-byte hash Poly1305 r ⁡ ( m ) {\displaystyle \operatorname {Poly1305} _{r}(m)} . To do this, Poly1305:

Interprets r {\displaystyle r} as a little-endian 16-byte integer. Breaks the message m = ( m [ 0 ] , m [ 1 ] , m [ 2 ] , … , m [ L − 1 ] ) {\displaystyle m=(m[0],m[1],m[2],\dotsc ,m[L-1])} into consecutive 16-byte chunks. Interprets the 16-byte chunks as 17-byte little-endian integers by appending a 1 byte to every 16-byte chunk, to be used as coefficients of a polynomial. Evaluates the polynomial at the point r {\displaystyle r} modulo the prime 2 130 − 5 {\displaystyle 2^{130}-5} . Reduces the result modulo 2 128 {\displaystyle 2^{128}} encoded in little-endian return a 16-byte hash. The coefficients c i {\displaystyle c_{i}} of the polynomial c 1 r q + c 2 r q − 1 + ⋯ + c q r {\displaystyle c_{1}r^{q}+c_{2}r^{q-1}+\cdots +c_{q}r} , where q = ⌈ L / 16 ⌉ {\displaystyle q=\lceil L/16\rceil } , are:

c i = m [ 16 i − 16 ] + 2 8 m [ 16 i − 15 ] + 2 16 m [ 16 i − 14 ] + ⋯ + 2 120 m [ 16 i − 1 ] + 2 128 , {\displaystyle c_{i}=m[16i-16]+2^{8}m[16i-15]+2^{16}m[16i-14]+\cdots +2^{120}m[16i-1]+2^{128},}

with the exception that, if L ≢ 0 ( mod 16 ) {\displaystyle L\not \equiv 0{\pmod {16}}} , then:

c q = m [ 16 q − 16 ] + 2 8 m [ 16 q − 15 ] + ⋯ + 2 8 ( L mod 1 6 ) − 8 m [ L − 1 ] + 2 8 ( L mod 1 6 ) . {\displaystyle c_{q}=m[16q-16]+2^{8}m[16q-15]+\cdots +2^{8(L{\bmod {1}}6)-8}m[L-1]+2^{8(L{\bmod {1}}6)}.}

… excerpt ends here. Continue reading the full article.

Worked examples

Example 1 — a first encounter with Poly1305

Start with the simplest possible case. Write down what Poly1305 claims or describes in one sentence, then invent the smallest concrete situation in which that sentence is true. In computer science, the smallest case is usually a single object, a single equation or a single measurement. Check that every symbol or term in your sentence has a meaning in that case.

Example 2 — changing one variable

Take the situation from Example 1 and change exactly one quantity: double it, halve it, or set it to zero. Predict what should happen to Poly1305 before you calculate. Comparing your prediction with the result is the fastest way to find out whether you understand the idea or only the words.

Example 3 — an exam-style question

Typical questions about Poly1305 ask you to (a) state it precisely, (b) apply it to given data, and (c) explain a limitation. Practise writing all three answers in under five minutes; the third part is what separates a full-mark answer from an average one.

Applications of Poly1305

In research: Poly1305 appears in computer science research whenever the underlying quantities have to be modelled precisely. Papers usually cite it as a starting assumption and then explore where it breaks down.
In technology and industry: Engineering practice reuses Poly1305 in design rules, simulations and safety margins. Knowing the idea lets you read a specification sheet and understand why the numbers look the way they do.
In the classroom: Poly1305 is common in secondary-school and first-year university syllabi. It links to neighbouring topics Advanced Encryption Standard, Internet Standards, Message authentication codes, so understanding it makes those chapters shorter.
In everyday life: Look for Poly1305 outside the textbook — in sport, cooking, traffic, electronics or the sky above you. An example you found yourself is remembered far longer than one you were given.

How to study Poly1305 in 20 minutes

Read the reference excerpt below once, without taking notes.
Close the page and write down what Poly1305 means in your own words.
Compare your version with the excerpt and mark what you missed.
Work through the three examples above with pen and paper.
Explain Poly1305 out loud to somebody else — or to Teacher Smith in the lgStudy chat.

Frequently asked questions

What is Poly1305 in simple terms?

Poly1305 is a universal hash family designed by Daniel J. Bernstein in 2002 for use in cryptography.

Why does Poly1305 matter?

Because it connects several computer science ideas at once: it gives you a definition you can apply, a quantity you can calculate, and a way to check whether a result is plausible.

How should I study Poly1305?

Read the excerpt, restate it from memory, then work through the examples and applications listed on this page. The five-step study plan above takes about twenty minutes.

What does this page cover?

It gives you a compact reference excerpt plus original lgStudy explanations, examples, applications and study material on Poly1305.