Not so long ago, at a muggle job, we had a question about storing private keys for various services. In the process, we found several solutions that were not very suitable for different reasons. I decided to come back to it sometime.

Requirements for the Service

For myself, I have highlighted a few requirements for this service to work:

• For now, the service must store a 256-bit private key (used in most blockchain networks)
• Should sign transactions and messages for EVM networks (support for other networks can be made later).
• A user can have an unlimited number of keys.
• A user's private key must not leave our service.
• Each key can be shared with an unlimited number of people.
• The keys we share must be unique.
• We should have a log of activity with each key.
• if the service that uses the sk If the key Is compromised, we should be able to revoke it.

Already in the process of work, when I realized how this task should be solved, I highlighted one more requirement:

• We must be able to limit the scope of each key. However, since the work was already in progress, I left it for the next article. Therefore, we will limit ourselves to signing the message within this article.

Options for Solving the Problem

Since the key will be used many times in the article, I will call the private key pk to avoid confusion and the key that is shared sk.

The initial option was to encrypt the key in the pbkdf2 function, but there was a problem with how to share the key to access the signature because we have only one key in the process of this algorithm.

I found two options to solve the problem:

1. We have a master key of the encrypted key stored in the database and have already shared the generated key, which leads to the original key. I wouldn't say I liked this option because if you get access to the database, the pk key is easy to decrypt.

2. We create a separate instance of our pk key for each key we check. I wouldn't say I like this option very much, either.

So, walking around and thinking about how to make the sk key convenient, I remembered that when using Shamir Secrets Sharing (SSS), you can make the sk key unique and share only a part of the key. The rest will be stored on the backend in security, and you can give these parts to anyone you want.

It would look like this: we encrypt the pk key with our SSS-generated key, store part of the key in different storages, and give part of the key to the user as sk. After about 10-15 minutes, I realized one straightforward thing:

When using SSS, we don't need to encrypt our pk key with anything else because SSS can handle it a little bit, and this solution is perfect for storing PK keys, in my opinion. It is always disassembled into parts using different storage options, including the user's. If it needs to be revoked, we delete the index information of our sk key and quickly assemble a new one.

In this article, I will not dwell on the principles of SSS; I have already written a short article on this topic and many principles from this article will form the basis of our new service.

Architecture

The principle of our service will be as follows:

1. The user chooses to generate a key.

2. We create a suitable key for the service. It will be our pk key. It never leaves the service as a whole.

3. Using SSS, we split our key so that three parts of the split key are required to recover the pk key. Each split key consists of two parts: x: the position of our key y: the value for this position

4. We throw the first part into Vault (it can be any service for storing sensitive information that can be accessed via API).

5. The second part we save to the database (I’m going to use PostgreSQL).

6. The third part we partially save to the database, and the other part we give to the user (sk). To use SK to find the value we need, we also save keccak256(sk) to the database. As far as I know, it has not been broken yet.

7. When the user needs to sign something, we collect the private key from different parts of the application and sign it.

This approach has one disadvantage, if the sk key administrator loses all his sk keys that were generated by him, we can't restore back the original key. As an option, you can make a backup of the original key, but that's for another time =).

Database

As a result of my work, I have this database structure:

• users stores information about the user aka key administrator.

• keys stores basic information about the key, such as the second part of our Share, the index by which you can find the first part of the Share in the Vault, and other information such as the address of our private key.

• shares contains a part of Share and also stores the hashed value of this Share. This is done so that we can find it in the database.

• logs any activity with the key, such as key creation and all signatures, falls here.

Realization

I used the Rust programming language with the Actix-web framework for this service. I use them all the time at work, so why not?

As I said, the database will be Postgresql for the following reasons.

Polynomial

lazy_static! {
    static ref PRIME: BigUint = BigUint::from_str_radix(
        "FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEBAAEDCE6AF48A03BBFD25E8CD0364141",
        16
    )
    .expect("N parse error");
}

#[derive(Clone, Debug)]
pub struct Share {
    pub x: BigUint,
    pub y: BigUint,
}

#[derive(Clone, Debug, Serialize, Deserialize)]
pub struct ShareStore {
    pub x: String,
    pub y: String,
}

impl From<Share> for ShareStore {
    fn from(share: Share) -> Self {
        ShareStore {
            x: hex::encode(share.x.to_bytes_be()),
            y: hex::encode(share.y.to_bytes_be()),
        }
    }
}

impl From<&Share> for ShareStore {
    fn from(share: &Share) -> Self {
        ShareStore {
            x: hex::encode(share.x.to_bytes_be()),
            y: hex::encode(share.y.to_bytes_be()),
        }
    }
}

pub struct Polynomial {
    prime: BigUint,
}

impl Polynomial {
    pub(crate) fn new() -> Self {
        Polynomial {
            prime: PRIME.clone(),
        }
    }

    // Calculates the modular multiplicative inverse of `a` modulo `m` using Fermat's Little Theorem.
    fn mod_inverse(&self, a: &BigUint, m: &BigUint) -> BigUint {
        a.modpow(&(m - 2u32), m) 
    }

    // Generates a random polynomial of a given degree with the secret as the constant term.
    fn random_polynomial(&self, degree: usize, secret: &BigUint) -> Vec<BigUint> {
        let mut coefficients = vec![secret.clone()];
        for _ in 0..degree {
            let index = BigUint::from_bytes_be(generate_random().as_slice());
            coefficients.push(index);
        }
        coefficients
    }

    // Evaluates a polynomial at a given point `x`, using Horner's method for efficient computation under a prime modulus.
    fn evaluate_polynomial(&self, coefficients: &[BigUint], x: &BigUint) -> BigUint {
        let mut result = BigUint::zero();
        let mut power = BigUint::one();
        for coeff in coefficients {
            result = (&result + (coeff * &power) % &self.prime) % &self.prime;
            power = (&power * x) % &self.prime;
        }
        result
    }

    // Generates `num_shares` shares from a secret, using a polynomial of degree `threshold - 1`.
    pub fn generate_shares(
        &self,
        secret: &BigUint,
        num_shares: usize,
        threshold: usize,
    ) -> Vec<Share> {
        let coefficients = self.random_polynomial(threshold - 1, secret);
        let mut shares = vec![];
        for _x in 1..=num_shares {
            let x = BigUint::from_bytes_be(generate_random().as_slice());
            let y = self.evaluate_polynomial(&coefficients, &x);
            shares.push(Share { x, y });
        }
        shares
    }

    // Reconstructs the secret from a subset of shares using Lagrange interpolation in a finite field.
    pub fn reconstruct_secret(&self, shares: &Vec<Share>) -> BigUint {
        let mut secret = BigUint::zero();
        for share_i in shares {
            let mut numerator = BigUint::one();
            let mut denominator = BigUint::one();
            for share_j in shares {
                if share_i.x != share_j.x {
                    numerator = (&numerator * &share_j.x) % &self.prime;
                    let diff = if share_j.x > share_i.x {
                        &share_j.x - &share_i.x
                    } else {
                        &self.prime - (&share_i.x - &share_j.x)
                    };
                    denominator = (&denominator * &diff) % &self.prime;
                }
            }
            let lagrange = (&share_i.y * &numerator * self.mod_inverse(&denominator, &self.prime))
                % &self.prime;
            secret = (&secret + &lagrange) % &self.prime;
        }
        secret
    }

    // Adds a new share to the existing set of shares using Lagrange interpolation in a finite field.
    pub fn add_share(&self, shares: &Vec<Share>) -> Share {
        let new_index = BigUint::from_bytes_be(generate_random().as_slice());
        let mut result = BigUint::zero();

        for share_i in shares {
            let mut lambda = BigUint::one();
            for share_j in shares {
                if share_i.x != share_j.x {
                    let numerator = if new_index.clone() >= share_j.x {
                        (new_index.clone() - &share_j.x) % &self.prime
                    } else {
                        (&self.prime - (&share_j.x - new_index.clone()) % &self.prime) % &self.prime
                    };

                    let denominator = if share_i.x >= share_j.x {
                        (&share_i.x - &share_j.x) % &self.prime
                    } else {
                        (&self.prime - (&share_j.x - &share_i.x) % &self.prime) % &self.prime
                    };

                    lambda = (&lambda * &numerator * self.mod_inverse(&denominator, &self.prime))
                        % &self.prime;
                }
            }
            result = (&result + &share_i.y * &lambda) % &self.prime;
        }

        Share {
            x: new_index,
            y: result,
        }
    }
}

I'll make a bit of a confession here: I'm not a mathematician. And while I tried to find as much information about this as I could, in fact, this is adapted code from my previous article.

You can read more about this feature here https://en.wikipedia.org/wiki/Lagrange_polynomial

This structure (or class, whichever is more convenient) performs the most important part of the process we described today - breaking the pk key into pieces and reassembling it again.

Create User

#[derive(Serialize, Deserialize)]
pub struct CreateUserResponse {
    pub secret: String,
}

pub async fn users_create_handler(app_data: web::Data<AppData>) -> HttpResponse {
    let code = generate_code();

    match create_user(
        CreateOrUpdateUser {
            secret: code.clone(),
        },
        app_data.get_db_connection(),
    )
    .await
    {
        Ok(_) => HttpResponse::Ok().json(CreateUserResponse { secret: code }),
        Err(e) => {
            return HttpResponse::InternalServerError().body(format!("Error creating user: {}", e));
        }
    }
}

Here, everything is as simple as possible; we create a user who has a master key to work with his keys. This is done to prevent any other party from doing anything with our keys. Ideally, this key should not be distributed in any way.

Generate Key

pub async fn keys_generate_handler(req: HttpRequest, app_data: web::Data<AppData>) -> HttpResponse {
    // Check if the request has a master key header
    let Some(Ok(master_key)) = req.headers().get(MASTER_KEY).map(|header| header.to_str()) else {
        return HttpResponse::Unauthorized().finish();
    };

    // Check if user with master key exist
    let user = match get_user_by_secret(&master_key, app_data.get_db_connection()).await {
        Ok(user) => user,
        Err(UserErrors::NotFound(_)) => {
            return HttpResponse::Unauthorized().finish();
        }
        Err(e) => {
            return HttpResponse::InternalServerError().body(format!("Error getting user: {}", e));
        }
    };

    // generate random `pk` private key
    let private_key = generate_random();
    let Ok(signer) = PrivateKeySigner::from_slice(private_key.as_slice()) else {
        return HttpResponse::InternalServerError().finish();
    };

    let secret = BigUint::from_bytes_be(private_key.as_slice());

    let poly = Polynomial::new();

    // divide `pk` key into 3 shares 
    let shares = poly
        .generate_shares(&secret, 3, 3)
        .iter()
        .map(Into::into)
        .collect::<Vec<ShareStore>>();
    
    // store first part at Vault
    let path = generate_code();

    if let Err(err) = kv2::set(
        app_data.get_vault_client().as_ref(),
        "secret",
        &path,
        &shares[0],
    )
    .await
    {
        return HttpResponse::InternalServerError().body(format!("Error setting secret: {}", err));
    }

    // Store second part at database and path to first share
    let key = CreateOrUpdateKey {
        user_id: user.id,
        local_key: shares[1].y.clone(),
        local_index: shares[1].y.clone(),
        cloud_key: path,
        address: signer.address(),
    };

    let key = match create_key(key, app_data.get_db_connection()).await {
        Ok(key) => key,
        Err(err) => {
            return HttpResponse::InternalServerError()
                .body(format!("Error creating key: {}", err));
        }
    };

    // Store third part at database as share
    let share = match create_share(
        CreateOrUpdateShare {
            secret: shares[2].y.clone(),
            key_id: key.id,
            user_index: shares[2].x.clone(),
            owner: SharesOwner::Admin,
        },
        app_data.get_db_connection(),
    )
    .await
    {
        Ok(share) => share,
        Err(err) => {
            return HttpResponse::InternalServerError()
                .body(format!("Error creating share: {}", err));
        }
    };

    let Ok(user_key) = hex::decode(&shares[2].y) else {
        return HttpResponse::InternalServerError().finish();
    };

    // Store log
    let _ = create_log(
        CreateLog {
            key_id: key.id,
            action: "generate_key".to_string(),
            data: serde_json::json!({
                "user_id": user.id
            }),
            message: None,
        },
        app_data.get_db_connection(),
    )
    .await;

    // Return the key and share identifier
    HttpResponse::Ok().json(KeysGenerateResponse {
        key: STANDARD.encode(user_key),
        id: share.id,
    })
}

Check the user that such a user exists, create a pk key, split it into parts, and save them in different places.

Grant Access

pub async fn keys_grant_handler(req: HttpRequest, app_data: web::Data<AppData>) -> HttpResponse {
    // Check if the request has a master key header
    let Some(Ok(master_key)) = req.headers().get(MASTER_KEY).map(|header| header.to_str()) else {
        return HttpResponse::Unauthorized().finish();
    };

    // Check if a user with the master key exists
    let user = match get_user_by_secret(&master_key, app_data.get_db_connection()).await {
        Ok(user) => user,
        Err(UserErrors::NotFound(_)) => {
            return HttpResponse::Unauthorized().finish();
        }
        Err(e) => {
            return HttpResponse::InternalServerError().body(format!("Error getting user: {}", e));
        }
    };

    // Check if the request has a secret key header
    let Some(Ok(secret_key)) = req.headers().get(SECRET_KEY).map(|header| header.to_str()) else {
        return HttpResponse::Unauthorized().finish();
    };
    
    let Ok(share) = STANDARD.decode(secret_key) else {
        return HttpResponse::Unauthorized().finish();
    };

    // Check if the share exists
    let share_value = hex::encode(share);
    let share = match get_share_by_secret(&share_value, app_data.get_db_connection()).await {
        Ok(share) => share,
        Err(ShareErrors::NotFound(_)) => return HttpResponse::NotFound().finish(),
        Err(_) => {
            return HttpResponse::Unauthorized().finish();
        }
    };
    
    if !matches!(share.status, SharesStatus::Granted) {
        return HttpResponse::Unauthorized().finish();
    }
    
    // Get original key with necessary information
    let key = match get_key_by_id(&share.key_id, app_data.get_db_connection()).await {
        Ok(key) => key,
        Err(KeyErrors::NotFound(_)) => return HttpResponse::NotFound().finish(),
        Err(_) => {
            return HttpResponse::Unauthorized().finish();
        }
    };

    // Check if the key belongs to the user
    if key.user_id != user.id {
        return HttpResponse::Unauthorized().finish();
    }

    // Get the first part of the key from Vault
    let Ok(cloud_secret) = kv2::read::<ShareStore>(
        app_data.get_vault_client().as_ref(),
        "secret",
        &key.cloud_key,
    )
    .await
    else {
        return HttpResponse::InternalServerError().finish();
    };

    // Combine the shares
    let shares = vec![
        Share {
            x: BigUint::from_str_radix(&cloud_secret.x, 16).expect("Error parsing local index"),
            y: BigUint::from_str_radix(&cloud_secret.y, 16).expect("Error parsing local key"),
        },
        Share {
            x: BigUint::from_str_radix(&key.local_index, 16).expect("Error parsing local index"),
            y: BigUint::from_str_radix(&key.local_key, 16).expect("Error parsing local key"),
        },
        Share {
            x: BigUint::from_str_radix(&share.user_index, 16).expect("Error parsing user index"),
            y: BigUint::from_str_radix(&share_value, 16).expect("Error parsing user key"),
        },
    ];

    let sss = Polynomial::new();
    
    // Create a new share
    let new_share = ShareStore::from(sss.add_share(&shares));

    // Store new share into database
    let share = match create_share(
        CreateOrUpdateShare {
            secret: new_share.y.to_string(),
            key_id: key.id,
            user_index: new_share.x.to_string(),
            owner: SharesOwner::Guest,
        },
        app_data.get_db_connection(),
    )
    .await
    {
        Ok(share) => share,
        Err(err) => {
            return HttpResponse::InternalServerError()
                .body(format!("Error creating share: {}", err));
        }
    };

    let Ok(user_key) = hex::decode(&new_share.y).map(|k| STANDARD.encode(k)) else {
        return HttpResponse::InternalServerError().finish();
    };

    // Store log
    let _ = create_log(
        CreateLog {
            key_id: key.id,
            action: "grant".to_string(),
            data: serde_json::json!({
                "user_id": user.id,
                "share_id": share.id,
            }),
            message: None,
        },
        app_data.get_db_connection(),
    )
    .await;

    // Return the key and share the identifier
    HttpResponse::Ok().json(KeysGenerateResponse {
        key: user_key,
        id: share.id,
    })
}

The mechanism of operation of this function is as follows:

We verify that the access requestor has all rights to the Share.

We need the secret key here for a very simple reason, without it we cannot recover the original pk key. Create an additional Share, and give it to the user.

Revoke Access

pub async fn keys_revoke_handler(
    req: HttpRequest,
    app_data: web::Data<AppData>,
    body: web::Json<KeysRevokeRequest>,
) -> HttpResponse {
    let Some(Ok(master_key)) = req.headers().get(MASTER_KEY).map(|header| header.to_str()) else {
        return HttpResponse::Unauthorized().finish();
    };

    let user = match get_user_by_secret(&master_key, app_data.get_db_connection()).await {
        Ok(user) => user,
        Err(UserErrors::NotFound(_)) => {
            return HttpResponse::Unauthorized().finish();
        }
        Err(e) => {
            return HttpResponse::InternalServerError().body(format!("Error getting user: {}", e));
        }
    };

    let share = match get_share_by_id(&body.id, app_data.get_db_connection()).await {
        Ok(share) => share,
        Err(ShareErrors::NotFound(_)) => return HttpResponse::NotFound().finish(),
        Err(_) => {
            return HttpResponse::Unauthorized().finish();
        }
    };

    let key = match get_key_by_id(&share.key_id, app_data.get_db_connection()).await {
        Ok(key) => key,
        Err(KeyErrors::NotFound(_)) => return HttpResponse::NotFound().finish(),
        Err(_) => {
            return HttpResponse::Unauthorized().finish();
        }
    };

    if key.user_id != user.id {
        return HttpResponse::Unauthorized().finish();
    }

    if revoke_share_by_id(&share.id, app_data.get_db_connection())
        .await
        .is_err()
    {
        return HttpResponse::InternalServerError().finish();
    }

    let _ = create_log(
        CreateLog {
            key_id: key.id,
            action: "revoke".to_string(),
            data: serde_json::json!({
                "user_id": user.id,
                "share_id": share.id,
            }),
            message: None,
        },
        app_data.get_db_connection(),
    )
    .await;

    HttpResponse::Ok().finish()
}

Here, we only need to know the identifier of the Share to which we are revoking access. In the future, if I do make a web interface, this will be easier to work with. We don't need our sk key here because we are not restoring the private key here.

Sign Message

#[derive(Deserialize, Serialize, Debug)]
pub struct SignMessageRequest {
    pub message: String,
}

#[derive(Deserialize, Serialize, Debug)]
pub struct SignMessageResponse {
    pub signature: String,
}

pub async fn sign_message_handler(
    app_data: web::Data<AppData>,
    req: HttpRequest,
    body: web::Json<SignMessageRequest>,
) -> HttpResponse {
    // Get the `sk` key from the request headers
    let Some(Ok(secret_key)) = req.headers().get(SECRET_KEY).map(|header| header.to_str()) else {
        return HttpResponse::Unauthorized().finish();
    };

    // restore shares
    let (shares, key_id, share_id) = match restore_shares(secret_key, &app_data).await {
        Ok(shares) => shares,
        Err(e) => {
            return HttpResponse::BadRequest().json(json!({"error": e.to_string()}));
        }
    };

    let sss = Polynomial::new();

    // restore `pk` key
    let private_key = sss.reconstruct_secret(&shares);

    //sign message
    let Ok(signer) = PrivateKeySigner::from_slice(private_key.to_bytes_be().as_slice()) else {
        return HttpResponse::InternalServerError().finish();
    };
    
    let Ok(signature) = signer.sign_message(body.message.as_bytes()).await else {
        return HttpResponse::InternalServerError().finish();
    };

    // create log
    let _ = create_log(
        CreateLog {
            key_id,
            action: "sign_message".to_string(),
            data: json!({
                "share_id": share_id,
            }),
            message: Some(body.message.clone()),
        },
        app_data.get_db_connection(),
    )
    .await;

    // return signature
    HttpResponse::Ok().json(SignMessageResponse {
        signature: hex::encode(signature.as_bytes()),
    })
}

Received the message, if everything was ok, recovered the private key, and signed the message with it.

Basically, the main methods of our application are described; I decided to take pity and not to put the whole code here. There is GitHub for that, and all the code will be available there =)

Conclusion

While this is still a draft of the application, it's important to note that it's not just a concept. it's a workable draft that shows promise. There are also integration tests in the repository to understand how it works. In the following parts, I plan to add the signature of transactions and make it possible to limit the scope of their use. I may then make a web interface and make this project friendly to the average person.

This development has quite a lot of potential for use, and I hope that I can reveal at least part of it; I apologize for these pages of code and sparse comments. I prefer to write code rather than explain what I wrote above. I will try to get better, but this is stronger now than I am.

Also, welcome comments on the code and PR if desired =)

Best wishes to all, and keep your private keys safe.