Heat oil in medium saucepan over medium heat until shimmering. Add onion, celery, carrot, and salt and stir to coat vegetables. Cover and cook, stirring occasionally, until vegetables are softened but not browned (8 to 10 minutes).

Add garlic, tomato paste, thyme, and pepper and cook, stirring constantly, until fragrant, about 2 minutes.

Stir in water and lentils. Increase heat and bring to boil. Adjust heat to simmer. Cover and cook, stirring occasionally, until lentils are tender but not mushy and have consistency of thick risotto (40 to 50 minutes). Remove from heat and keep covered.

While the lentils are cooking, dissolve the salt in 1 quart of water in narrow container. Submerge the salmon in the brine and let stand for 15 minutes, then remove the salmon and pat dry with paper towels. Allow to stand while lentils finish cooking.

Sprinkle the bottom of a cold 12-inch nonstick skillet evenly with 1/2 tsp salt and 1/2 tsp pepper. Place the fillets, skin side down, in the skillet and sprinkle the tops of fillets with the remaining 1/4 tsp salt and 1/4 teaspoon pepper. Heat the skillet over medium-high heat and cook fillets, without moving them, until fat begins to render, skin begins to brown, and the bottom 1/4 inch of the fillets turns opaque (6 to 8 minutes).

Using tongs and thin spatula, flip the fillets and continue to cook without moving them until centers are still translucent when checked with tip of paring knife and register 125 F (5 to 8 minutes longer). Transfer the fillets, skin side up, to clean plate.

Warm the lentils briefly if necessary. Stir in vinegar, mustard, and remaining 1 tablespoon oil. Season with salt, pepper, and vinegar to taste. Divide the lentils among wide, shallow serving bowls. Arrange salmon skin side up on lentils and serve.