# US 9,882,717 B2 · System and method for generating a server-assisted strong password from a weak secret

> Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt

- Number: US 9,882,717 B2
- Document ID: US9882717B2
- Status: Granted
- Kind: B2
- Application number: 15/226,064
- Filed: 2016-08-02
- Published: 2017-08-03
- Granted: 2018-01-30
- Earliest claimed: 2016-02-02
- Assignees: International Business Machines Corporation
- Applicants: International Business Machines Corporation
- Inventors: Jan L. Camenisch; Franz-Stefan Preiss; Kai Samelin; Dieter M. Sommer
- Web page: https://patentgrep.com/patent/US9882717B2

## CPC

- H04L 9/0861: {Generation of secret information including derivation or calculation of cryptographic keys or passwords}
- H04L 9/085: {Secret sharing or secret splitting, e.g. threshold schemes}
- H04L 9/0863: {involving passwords or one-time passwords (network architectures or network communication protocols for using one-time keys in a packet data network H04L63/067)}
- H04L 9/0894: {Escrow, recovery or storing of secret information, e.g. secret key escrow or cryptographic key storage}
- H04L 9/3247: {involving digital signatures}
- H04L 63/061: {for key exchange, e.g. in peer-to-peer networks (cryptographic mechanisms or cryptographic arrangements for key agreement H04L9/0838)}
- H04L 63/0815: {providing single-sign-on or federations}
- H04L 63/083: {using passwords (cryptographic mechanisms or cryptographic arrangements for entity authentication using a predetermined code H04L9/3226)}
- H04L: TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION (arrangements common to telegraphic and telephonic communication H04M)

## Abstract

Disclosed herein is a method for generating a high entropy password using a low entropy password and low-entropy login data comprising supplying the low entropy password to a system comprising a generating client and/or a recovery client; and at least n servers; submitting request data derived, at least in part, from the user's low entropy password, where the request data includes authentication data; engaging in a distributed protocol with at least t servers to generate high-entropy values based on stored cryptographic information and a set of authentication information stored on the at least n servers which is checked against the authentication data provided by the user and/or the generating client and/or a recovery client; and generating the high entropy password.

## Claims

### Claim 1

A method for generating a high entropy password using a low entropy password and low-entropy login data comprising:
supplying the low entropy password to a system comprising:
a generating computer client and/or a recovery computer client, and
at least n computer servers;
submitting request data derived, at least in part, from the user's low entropy password, where the request data includes authentication data; where a user enters the low entropy password into the generating computer client and/or recovery computer client;
engaging in a distributed protocol with at least t computer servers to generate high-entropy values based on stored cryptographic information and a set of authentication information stored on the at least n computer servers which is checked against the authentication data provided by the user and/or the generating computer client and/or a recovery computer client; and
generating the high entropy password where at least a threshold t≦n of the at least n computer servers contribute to generation of the high-entropy password, where a corrupted computer server cannot generate any passwords after a single setup as long as the threshold t≦n is not reached.

### Claim 2 (depends on 1)

The method of claim 1, further comprising permitting the user to provide a plurality of auxiliary low entropy passwords that permit deriving a plurality of high entropy passwords for a plurality of different services and where the at least t computer servers do not learn the plurality of auxiliary passwords.

### Claim 3 (depends on 2)

The method of claim 2, where none of the at least n computer servers learn which high entropy password was generated in a given password generating session.

### Claim 4 (depends on 3)

The method of claim 3, further comprising permitting the at least n computer servers to stop contributing to high entropy password generation.

### Claim 5 (depends on 4)

The method of claim 4, where the system further comprises a recovery computer client that contributes to password generation, and where the recovery computer client authenticates itself towards the at least n computer servers to avoid flooding the at least n computer servers with false login attempts.

### Claim 6 (depends on 1)

The method of claim 1, where the generating computer client and/or recovery computer client communicates with the at least n computer servers to generate a RSA-key pair (d, (N, e)), where d, N and e represent integers and where the relationship between d, N and e is given by equation (1):
(d)e≡1 mod φ(N) (1),
splitting up the integer d into a plurality of key-shares;
assigning a portion of each key-share di to the one or more computer servers as seen in the Equation (2); where n is an integer that represents a number of computer servers;
(d1d2d3 . . . dn)e≡1 mod φ(N) (2),
where di is a share of the ith computer server;
sending initial data that comprises derived data from the low entropy password PW, the RSA-key pair, a salt k, and an optional “id” from the generating computer client and/or recovery computer client to the one or more computer servers; where initial data is represented by Equation (3)
id,h1=H(k,PW,S1)d1,N (3), and
computing a bit string (N, e, di, id) which constitutes the computer server secrets; where the bit string is computed by the at least n computer servers, or a combination of the none or more of the at least n computer servers and the generating computer client.

### Claim 7 (depends on 6)

The method of claim 6, where n>2 or where n=t−1, and where the user takes a RSA-key share.

### Claim 8 (depends on 6)

The method of claim 6, where n=t is greater than or equal to 2 when a user does not take a RSA-key pair share.

### Claim 9 (depends on 6)

The method of claim 6, where n≧1 or where n=t−1, and where the user takes a RSA-key share.

### Claim 10 (depends on 9)

The method of claim 9, where a first computer server sends to the generating computer client and/or recovery computer client a first signature s1←sod1 mod N, where d1 is a share of the first computer server; where so=H(m)re mod N is a blinded signature or a value obtained from an oblivious pseudorandom function.

### Claim 11 (depends on 10)

The method of claim 10, where the nth computer server sends to the generating computer client and/or recovery computer client an nth signature sn, where sn=sn-1r−1 mod N is a blinded signature or a signature obtained from an oblivious pseudorandom function and where r is coprime with N.

### Claim 12

A system comprising:
a generating computer client and/or recovery computer client in operative communication with a user; where the user provides a password to the generating computer client and/or recovery computer client; and
a computer server; where the computer server is in operative communication with the generating computer client and/or recovery computer client; and
where the generating computer client and/or recovery computer client:
generates a RSA-key pair (d, (N, e)), where d, N and e represent integers and where the relationship between d, N and e is given by equation (1):
(d)e≡1 mod φ(N) (1),
splits up the integer d into a plurality of key-shares;
assigns a portion of each key-pair share di to the one or more computer servers as seen in the Equation (2); where n is an integer that represents a number of computer servers;
(d1d2d3 . . . dn)e≡1 mod φ(N) (2),
where di is a share of the ith computer server; where n is an integer that represents the number of computer servers;
sends initial data that is derived from the low entropy password PW, the RSA-key pair, a salt k, and an optional “id” from the generating computer client and/or recovery computer client to the one or more computer servers; where initial data is represented by Equation (3)
id,h1=H(k,PW,S1)d1,N (3), and
computes a bit string (N, e, di, id) which provides the high entropy password; where the bit string is computed by the at least n computer servers, or a combination of the one or more of the at least n computer servers and the generating computer client.

### Claim 13 (depends on 12)

The system of claim 12, where n≧1 if a user takes a RSA-key pair share di for himself.

### Claim 14 (depends on 13)

The system of claim 13, where a first computer server sends to the generating computer client and/or the recovery computer client a first signature s1←sod1 mod N, where d1 is a share of the first computer server; where so is a blinded signature or a signature obtained from an oblivious pseudorandom function.

### Claim 15 (depends on 14)

The system of claim 14, where the nth computer server sends to the generating computer client and/or recovery computer client an nth signature snr−1 mod N, where sn is a blinded signature or a signature obtained from an oblivious pseudorandom function and where r is coprime with N and where snr−1 mod N is the high entropy password that can be verified on inspection.

### Claim 16 (depends on 12)

The system of claim 12, where n is greater than or equal to 2 when a user does not take a RSA-key pair share.