Method for generating a broadcast challenge value

• US 6,285,873 B1
• Filed: 03/09/1998
• Issued: 09/04/2001
• Est. Priority Date: 03/09/1998
• Status: Expired due to Term

• Current Assignee: Qualcomm, Inc.
• Original Assignee: Qualcomm, Inc.
• Inventors: Quick, Roy F. Jr.
• Primary Examiner(s): Hunter, Daniel
• Assistant Examiner(s): Woldetatios, Yemane
• Application Number:
  US09/036,941
• Time in Patent Office: 1,275 Days
• Field of Search: 455/410, 455/411, 455/422, 455/412, 455/414, 455/415, 455/458, 455/461, 455/511, 455/515, 455/561, 455/419, 380/247, 380/248, 380/249
• US Class Current: 455/422.1
• CPC Class Codes: H04L 2209/80 Wireless network architectures or network communication protocols for wireless network security H04W12/00
• CPC Class Codes: H04L 9/3271 using challenge-response
• CPC Class Codes: H04W 12/062 Pre-authentication

Abstract

A method for generating a broadcast challenge value includes the steps of applying a first updating algorithm to the most significant bits of the broadcast challenge value, and applying a second, distinct updating algorithm to the least significant bits of the broadcast challenge value. The updating algorithms can be maximal-length shift registers or other forms of pseudorandom noise generator. The sequence of successive unrepeated values can be extended for either one or both sets of bits by inserting an all-zeroes value once during the period of time before which an update value recurs. System-wide synchronization can be achieved via a global time reference.

Claims

1. A method of updating a broadcast challenge value transmitted by a cellular base station on a control channel, comprising the steps of:

applying a first updating algorithm to a plurality of most significant bits of the broadcast challenge value; and

operating on a plurality of least significant bits of the broadcast challenge value with a second updating algorithm to generate an updated broadcast challenge value.

2. The method of claim 1, wherein the applying step comprises applying a first maximal-length shift register algorithm.

3. The method of claim 1, wherein the applying step comprises applying a first pseudorandom noise generation algorithm.

4. The method of claim 1, wherein the operating step comprises operating on the plurality of least significant bits with a second maximal-length shift register algorithm.

5. The method of claim 1, wherein the operating step comprises operating on the plurality of least significant bits with a second pseudorandom noise generation algorithm.

6. The method of claim 1, wherein the applying step comprises applying a first updating algorithm that inserts an all-zeroes value as an update for the plurality of most significant bits once during the period of time necessary for the sequence of updates to produce a repeat value for the plurality of most significant bits.

7. The method of claim 1, wherein the operating step comprises operating on the plurality of least significant bits with a second updating algorithm that inserts an all-zeroes value as an update for the plurality of least significant bits once during the period of time necessary for the sequence of updates to produce a repeat value for the plurality of least significant bits.

8. The method of claim 1, wherein the applying step comprises applying a first updating algorithm that ensures that every update value for the plurality of most significant bits is a nonzero value.

9. The method of claim 1, wherein the operating step comprises operating on the plurality of least significant bits with a second updating algorithm that ensures that every update value for the plurality of least significant bits is a nonzero value.

10. In a cellular system, a method of synchronously updating binary numbers used by a plurality of base stations to authenticate a plurality of mobile subscriber units, the method comprising the steps of:

applying a first updating algorithm to a plurality of most significant bits of the binary number for each of the plurality of base stations;

operating on a plurality of least significant bits of the binary number for each of the plurality of base stations with a second updating algorithm; and

synchronizing across the plurality of base stations update values of the binary numbers that result from the applying and operating steps.

11. The method of claim 10, wherein the synchronizing step is accomplished with a system-wide time reference available to the plurality of base stations.

12. The method of claim 11, wherein the system-wide time reference is GPS time.

13. The method of claim 11, wherein the applying step comprises applying a first maximal-length shift register algorithm.

14. The method of claim 11, wherein the applying step comprises applying a first pseudorandom noise generation algorithm.

15. The method of claim 11, wherein the operating step comprises operating on the plurality of least significant bits with a second maximal-length shift register algorithm.

16. The method of claim 11, wherein the operating step comprises operating on the plurality of least significant bits with a second pseudorandom noise generation algorithm.

17. The method of claim 11, wherein the applying step comprises applying a first updating algorithm that inserts an all-zeroes value as an update for the plurality of most significant bits once during the period of time necessary for the sequence of updates to produce a repeat value for the plurality of most significant bits.

18. The method of claim 11, wherein the operating step comprises operating on the plurality of least significant bits with a second updating algorithm that inserts an all-zeroes value as an update for the plurality of least significant bits once during the period of time necessary for the sequence of updates to produce a repeat value for the plurality of least significant bits.

19. The method of claim 11, wherein the applying step comprises applying a first updating algorithm that ensures that every update value for the plurality of most significant bits is a nonzero value.

20. The method of claim 11, wherein the operating step comprises operating on the plurality of least significant bits with a second updating algorithm that ensures that every update value for the plurality of least significant bits is a nonzero value.

21. A cellular base station, comprising:

an integrated circuit capable of running software; and

a set of software instructions executed by the integrated circuit for applying a first updating algorithm to a plurality of most significant bits of a binary number and for applying a second updating algorithm to a plurality of least significant bits of the binary number to generate an updated binary number.

22. The base station of claim 21, wherein the first updating algorithm comprises a first simulated maximal-length shift register algorithm.

23. The base station of claim 21, wherein the first updating algorithm comprises a first pseudorandom noise generation algorithm.

24. The base station of claim 21, wherein the second updating algorithm comprises a second simulated maximal-length shift register algorithm.

25. The base station of claim 21, wherein the second updating algorithm comprises a second pseudorandom noise generation algorithm.

26. The base station of claim 21, wherein the first updating algorithm inserts an all-zeroes value as an update for the plurality of most significant bits once during the period of time necessary for the sequence of updates to produce a repeat value for the plurality of most significant bits.

27. The base station of claim 21, wherein the second updating algorithm inserts an all-zeroes value as an update for the plurality of least significant bits once during the period of time necessary for the sequence of updates to produce a repeat value for the plurality of least significant bits.

28. The base station of claim 21, wherein the first updating algorithm ensures that every update value for the plurality of most significant bits is a nonzero value.

29. The base station of claim 21, wherein the second updating algorithm ensures that every update value for the plurality of least significant bits is a nonzero value.

30. A cellular system, comprising:

a system-wide time reference signal;

a plurality of mobile subscriber units; and

a plurality of base stations configured for wireless communication with the plurality of mobile subscriber units, each of the plurality of base stations comprising;

an integrated circuit capable of running software; and

a set of software instructions executed by the integrated circuit for applying a first updating algorithm to a plurality of most significant bits of a binary number and for applying a second updating algorithm to a plurality of least significant bits of the binary number, the binary number serving to authenticate any mobile subscriber unit requesting communication with a base station, and for synchronizing successive update values of the binary numbers with the system-wide time reference signal across the plurality of base stations.

31. The cellular system of claim 30, wherein the system-wide time reference signal conveys to each of the plurality of base stations a measure of GPS time.

32. The cellular system of claim 30, wherein the first updating algorithm comprises a first simulated maximal-length shift register algorithm.

33. The cellular system of claim 30, wherein the first updating algorithm comprises a first pseudorandom noise generation algorithm.

34. The cellular system of claim 30, wherein the second updating algorithm comprises a second simulated maximal-length shift register algorithm.

35. The cellular system of claim 30, wherein the second updating algorithm comprises a second pseudorandom noise generation algorithm.

36. The cellular system of claim 30, wherein the first updating algorithm inserts an all-zeroes value as an update for the plurality of most significant bits once during the period of time necessary for the sequence of updates to produce a repeat value for the plurality of most significant bits.

37. The cellular system of claim 30, wherein the second updating algorithm inserts an all-zeroes value as an update for the plurality of least significant bits once during the period of time necessary for the sequence of updates to produce a repeat value for the plurality of least significant bits.

38. The cellular system of claim 30, wherein the first updating algorithm ensures that every update value for the plurality of most significant bits is a nonzero value.

39. The cellular system of claim 30, wherein the second updating algorithm ensures that every update value for the plurality of least significant bits is a nonzero value.

40. A base station, comprising:

first means for updating a plurality of most significant bits of a broadcast challenge value; and

second means for updating a plurality of least significant bits of the broadcast challenge value to generate an updated binary number.

41. The base station of claim 40, wherein the first means for updating comprises a first simulated maximal-length shift register.

42. The base station of claim 40, wherein the first means for updating comprises a first pseudorandom noise generator.

43. The base station of claim 40, wherein the second means for updating comprises a second simulated maximal-length shift register.

44. The base station of claim 40, wherein the second means for updating comprises a second pseudorandom noise generator.

45. The base station of claim 40, wherein the first means for updating comprises inserting an all-zeroes value as an update for the plurality of most significant bits once during the period of time necessary for the sequence of updates to produce a repeat value for the plurality of most significant bits.

46. The base station of claim 40, wherein the second means for updating comprises inserting an all-zeroes value as an update for the plurality of least significant bits once during the period of time necessary for the sequence of updates to produce a repeat value for the plurality of least significant bits.

47. The base station of claim 40, wherein the first means for updating comprises ensuring that every update value for the plurality of most significant bits is a nonzero value.

48. The base station of claim 40, wherein the second means for updating comprises ensuring that every update value for the plurality of least significant bits is a nonzero value.

49. A cellular system, comprising:

means for establishing system-wide time synchronization;

a plurality of mobile subscriber units; and

a plurality of base stations configured for wireless communication with the plurality of mobile subscriber units, each of the plurality of base stations comprising;

first means for updating a plurality of most significant bits of a binary number, the binary number serving to authenticate any mobile subscriber unit requesting communication with a base station;

second means for updating a plurality of least significant bits of the binary number; and

means for synchronizing successive update values of the binary numbers across the plurality of base stations with the means for establishing system-wide time synchronization.

50. The cellular system of claim 49, wherein the means for establishing system-wide time synchronization conveys to each of the plurality of base stations a measure of GPS time.

51. The cellular system of claim 49, wherein the first means for updating comprises a first simulated maximal-length shift register.

52. The cellular system of claim 49, wherein the first means for updating comprises a first pseudorandom noise generator.

53. The cellular system of claim 49, wherein the second means for updating comprises a second simulated maximal-length shift register.

54. The cellular system of claim 49, wherein the second means for updating comprises a second pseudorandom noise generator.

55. The cellular system of claim 49, wherein the first means for updating inserts an all-zeroes value as an update for the plurality of most significant bits once during the period of time necessary for the sequence of updates to produce a repeat value for the plurality of most significant bits.

56. The cellular system of claim 49, wherein the second means for updating inserts an all-zeroes value as an update for the plurality of least significant bits once during the period of time necessary for the sequence of updates to produce a repeat value for the plurality of least significant bits.

57. The cellular system of claim 49, wherein the first means for updating ensures that every update value for the plurality of most significant bits is a nonzero value.

58. The cellular system of claim 49, wherein the second means for updating ensures that every update value for the plurality of least significant bits is a nonzero value.