Methods and system for secure communication between an RFID tag and a reader

Patent metadata

Field	Value
Publication number	US-9490970-B2
Application number	US-201514962179-A
Country	US
Kind code	B2
Filing date	Dec 8, 2015
Priority date	Mar 16, 2012
Publication date	Nov 8, 2016
Grant date	Nov 8, 2016

Abstract

Methods and a system involve secure communication between an RFID tag and a reader via the over-the-air interface, and to corresponding RFID tags and corresponding readers. A modification of the Rabin method is employed wherein within the framework of the encryption of a plaintext M into which an identification element of the RFID tag or of an object furnished therewith is incorporated, there is computed by the RFID tag, the Montgomery residue (Montgomery reduction) of the square of the plaintext M modulo n with respect to a Montgomery base R, i.e. C*=M 2 R −1 mod n, and the resultant ciphertext C* is employed for authenticating the RFID tag. The modulus n=p·q is the public key of the reader, the prime numbers p, q are the private key of the reader, and the Montgomery base R is an integer that is larger than the modulus n.

First claim

The invention claimed is:

1. A method for secure communication between a radio frequency identification (RFID) tag and an RF reader, the RFID tag comprising a storage unit and a processor unit, and the RF reader comprising a storage unit and a processor unit, wherein the method comprises:
the RFID tag encrypting a plaintext M, into which an identification element (UII) of the RFID tag is incorporated, for computing a ciphertext C* by computing a Montgomery residue of a square of the plaintext M modulo n with respect to a Montgomery base R, i.e. C*=M 2 R −1 mod n, and
after encrypting the plaintext M, the RFID tag sends an authentication message over-the-air to the RF reader, the authentication message being based on the ciphertext C*,
the RF reader receiving, recording and processing the authentication message in order to interpret the secure communication,
wherein the RF reader uses a modulus n=p·q as a public key, prime numbers p, q as a private key, and the Montgomery base R as an integer that is larger than the modulus n
wherein data incorporated into the plaintext M is scrambled by means of an interleaving operation in order to distribute random data stemming from the RF reader and from the RFID tag randomly over the plaintext M.

2. The method according to claim 1 , wherein the authentication message transferred from the RFID tag to the reader contains the encrypted plaintext M in a form of the ciphertext C* with C*=M 2 R−1 mod n.

3. The method according to claim 1 , wherein there are further incorporated into the plaintext M a first random number RND 1 generated by the reader and a second random number RND 2 generated by the RFID tag, wherein the first random number RND 1 is transferred to the RFID tag as a challenge within a framework of a challenge-response method.

4. The method according to claim 3 , wherein the RFID tag is configured such that the RFID tag can begin with an encryption during a read-in of the challenge in form of the first random number RND 1 , and first bytes of the computed ciphertext C* can already be output to the reader while subsequent bytes of the ciphertext C* are still being computed.

5. The method according to claim 1 , wherein there is further incorporated into the plaintext M a digital signature (SIG(UII)) of the identification element (UII) of the RFID tag, which is deposited in a storage unit of the RFID tag and can be checked by the reader.

6. The method according to claim 1 , wherein the modulus n is chosen, for saving computing time, as follows: n=1(mod 2bl·nd), where nd is an integer with 1≦nd<d, bl is a word width of the processor unit of the RFID tag, and d is a length of the modulus n in word widths of the processor unit.

7. The method according to claim 1 , wherein the Montgomery base R is chosen for a given modulus n as follows: R=2bl·(d+sd), where bl is a word width of the processor unit of the RFID tag, d is a length of the modulus n in word widths of the processor unit, and sd is a security parameter which is so chosen that it holds that bl·sd≧1.

8. A method for secure communication between a radio frequency identification (RFID) tag and an RF reader, the RF reader comprising a storage unit and a processor unit, and the RFID tag comprising a storage unit and a processor unit, wherein the method comprises:
the RF reader receiving over-the-air from the RFID tag an authentication message which is based on a ciphertext, i.e. C*=M 2 R −1 mod n, comprising an encrypted plaintext M, which was encrypted by the RFID tag, into which an identification element (UII) of the RFID tag has been incorporated, and
after receiving the plaintext M, the RF reader decrypts the encrypted plaintext M, a decrypting step comprising multiplying the encrypted plaintext M by a Montgomery base R and subsequently carrying out a modulo operation with the modulus n,
wherein the RF reader uses a modulus n=p·q as a public key, prime numbers p, q as a private key, and the Montgomery base R as an integer that is larger than the modulus n,
wherein data incorporated into the plaintext M is scrambled by means of an interleaving operation in order to distribute random data stemming from the RF reader and from the RFID tag randomly over the plaintext M.

9. The method according to claim 8 , wherein the authentication message transferred from the RFID tag to the reader contains the encrypted plaintext M in a form of the ciphertext C* with C*=M 2 R−1 mod n.

10. The method according to claim 8 , wherein there are further incorporated into the plaintext M a first random number RND 1 generated by the reader and a second random number RND 2 generated by the RFID tag, wherein the first random number RND 1 is transferred to the RFID tag as a challenge within a framework of a challenge-response method.

11. The method according to claim 10 , wherein the RFID tag is configured such that the RFID tag can begin with an encryption during a read-in of the challenge in form of the first random number RND 1 , and first bytes of the computed ciphertext C* can already be output to the reader while subsequent bytes of the ciphertext C* are still being computed.

12. The method according to claim 8 , wherein there is further incorporated into the plaintext M a digital signature (SIG(UII)) of the identification element (UII) of the RFID tag, which is deposited in a storage unit of the RFID tag and can be checked by the reader.

13. The method according to claim 8 , wherein the modulus n is chosen, for saving computing time, as follows: n=1(mod 2bl·nd), where nd is an integer with 1≦nd<d, bl is a word width of a processor unit of the RFID tag, and d is a length of the modulus n in word widths of the processor unit.

14. The method according to claim 8 , wherein the Montgomery base R is chosen for a given modulus n as follows: R=2bl·(d+sd), where bl is a word width of a processor unit of the RFID tag, d is a length of the modulus n in word widths of the processor unit, and sd is a security parameter which is so chosen that it holds that bl·sd≧1.

15. A radio frequency identification (RFID) tag for secure communication with RF reader,
wherein the RFID tag comprises a processor and memory into which an identification element (UII) is deposited, and wherein the processor is configured for encrypting a plaintext M into which the identification element (UII) of the RFID tag is incorporated, for computing a ciphertext C* by computing a Montgomery residue of a square of the plaintext M modulo n with respect to a Montgomery base R, i.e. C*=M 2 R −1 mod n, and
transmitting an authentication message over-the-air to the RF reader, the authentication message being based on the ciphertext C*,
wherein modulus n=p·q is a public key of the RF reader, prime numbers p, q are a private key of the RF reader, and the Montgomery base R is an integer that is larger than the modulus n,
wherein data incorporated into the plaintext M is scrambled by means of an interleaving operation in order to distribute random data stemming from the RF reader and from the RFID tag randomly over the plaintext M.

16. An radio frequency (RF) reader for secure communication with a radio frequency identification (RFID) tag:
wherein the RF reader comprises memory and a processor which is configured for receiving over-the-air from the RFID tag an authentication message which is based on a ciphertext, i.e. C*=M 2 R −1 mod n, comprising an encrypted plaintext M, which was encrypted by the RFID tag, into which an identification element (UM) of the RFID tag has been incorporated, and
decrypting the encrypted plaintext M, wherein upon decryption the encrypt

Assignees

• Giesecke & Devrient Gmbh

Inventors

• Hinz Walter
• Finkenzeller Klaus
• Seysen Martin

Classifications

• H04L9/302 Primary

  involving the integer factorization problem, e.g. RSA or quadratic sieve [QS] schemes · CPC title

• H04L2209/805

  Lightweight hardware, e.g. radio-frequency identification [RFID] or sensor · CPC title

• H04L2209/08

  Randomization, e.g. dummy operations or using noise · CPC title

• H04L2209/72

  Signcrypting, i.e. digital signing and encrypting simultaneously · CPC title

• H04L9/3271

  using challenge-response · CPC title